백준 5582. 공통 부분 문자열

https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

 

 

아래 문제와 거의 유사한데 살짝 다른 문제.

https://tose33.tistory.com/111

백준 9251. LCS

9251. LCS 문제는 Longest Common Subsequence, 최장 공통 부분 수열을 구하는 문제였다. 

즉 두 수열이 주어졌을때 두 수열의 부분 수열(연속하지 않아도됨) 중 가장 긴 부분수열을 구하는 문제다.

 

이번 문제 5582. 공통 부분 문자열은 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열(연속해야함)을 구해야 한다. 

 

두 문자열이 다음과 같다면 가장 긴 공통 부분 문자열은 ADABR 이다. 

ABRACADABRA
ECADADABRBCRDARA

 

d[i][j] :

문자열 A의 길이가 i, 문자열 B의 길이가 j 일때 A[i]와 B[j]가 같다면 해당 문자로 끝나는 공통 부분 문자열의 길이 

 

이게 무슨 말이냐면, d[2][8] 이라면 A 문자열은 ABR, B 문자열은 ECADADABR 이다. 

가장 끝 문자가 같으니, 가장 끝 문자인 R에서 부터 뒤로 카운트 했을때 공통 부분 문자열은 ABR이니까 d[2][8] = 3이다. 

 

점화식은 if(A[i-1] == B[j-1]) d[i][j] = d[i-1][j-1] + 1 

 

d[i-1][j-1]+1인 이유는 A와 B의 마지막 문자가 같다면 두 문자열의 마지막 문자를 제외한 문자열들에서 마지막 문자를 추가했기 때문이다.