문제
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.
어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.
두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.
https://www.acmicpc.net/problem/5582
입력
첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.
출력
첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.
풀이
이 문제에서는, "연속된 공통 부분 문자열" 중에서 가장 큰 길이를 출력하는 것이다. 즉 붙어있어야만 인정됨을 유의하고 풀었다.
2차원 dp배열을 초기화 하고, 2중 for문을 통해 각 문자열을 하나씩 비교하며 같으면 dp배열에 값을 업데이트 하는 방식으로 접근하면 된다. 업데이트 하는 조건은 다음과 같다.
if(a[i] == b[j])
if(i == 0 || j ==0)
dp[i][j] = 1
else dp[i][j] = dp[i-1][j-1] + 1두 문자가 같을 때, i-1,j-1의 값에 1을 더하는데, 만약 i또는 j가 0일때 두 문자가 같은 경우는 0이 아니라 1로 지정해줘야 한다. 범위를 벗어나는 경우에 대한 처리.
위 조건을 알아봄과 동시에 c++ 음수 인덱스에 대해서 알아보았는데, vector의 경우 out of bound에 대한 체크를 해주지만, array의 경우 체크를 하지 않는다. 따라서 범위를 벗어나게 된다면 undefined behaviour로 이어진다.
[참고] https://stackoverflow.com/questions/47170740/c-negative-array-index
