백준 5582. 공통 부분 문자열
https://www.acmicpc.net/problem/5582
5582번: 공통 부분 문자열
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들
www.acmicpc.net
아래 문제와 거의 유사한데 살짝 다른 문제.
https://tose33.tistory.com/111
백준 9251. LCS
www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAY..
tose33.tistory.com
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의 마지막 문자가 같다면 두 문자열의 마지막 문자를 제외한 문자열들에서 마지막 문자를 추가했기 때문이다.