LCS란

LCS란 두가지가 있다.

• LCS (Longest Common Substring) = 최장 공통 부분 문자열
• LCS (Longest Common Subsequence) = 최대 공통 부분 수열

예를 들어 abcd, abdd가 있으면
Longest Common Subsequence는 abd이므로 길이가 3이 되고
Longest Common Substring는 말그대로 Substring이기 때문에 연속되는 문자열 ab이며 길이는 2가 된다.

기본적인 풀이

2차원 배열을 이용하여 dp table을 생성 후 두 문자 하나하나를 비교하며 맨 앞에부터 차례대로 채워가는 방식을 사용합니다.
i==0 || j==0 일 때 0이란 값을 초기화하여 시작점을 초기화합니다.
subproblem으로 확인하는 것이 중요합니다.

---

LCS (Longest Common Substring) 최장 공통 부분 문자열

로직

• 비교하는 문자가 같으면 [i-1, j-1] + 1
• 비교하는 문자가 다르면 0

코드

if (i == 0 || j == 0){ // 시작점 초기화
	LCS[i][j] = 0
    }
else if (a[i]==b[i]){ 
	dp[i][j] = dp[i - 1][j - 1] + 1
    }
else{
	LCS[i][j] = 0
}
	

---

LCS (Longest Common Subsequence) 최대 공통 부분 수열

로직

• 비교하는 문자가 같으면 [i-1, j-1] + 1
• 비교하는 문자가 다르면 max([i-1, j], [i, j-1])

코드

두개의 문자열 a, b가 있을 때 Longest Common Subsequence를 구하는 간단한 문제의 코드입니다.

string a, b;
		cin >> a >> b;
		int sizeA = a.size();
		int sizeB = b.size();
		for (int i = 1; i <= sizeB; i++) {
			for (int j = 1; j <= sizeA; j++) {
				if (a[j-1] == b[i-1]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				else {
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				}
				if (ans < dp[i][j]) {
					ans = dp[i][j];
				}
			}
		}