LCS

---

LCS(Longest Common Subsequence)란

한글로 번역하면 최장 공통 부분수열이다. 비슷한 개념으로는 최장 공통 문자열(Longest Common Substring)이 있다.

후자는 말그대로, 두 문자열중 공통되는 문자열이 연속으로 이어지는 문자열을 말한다.

ACAYKP와 CAPCAK의 최장 공통 부분수열은 ACAK
ACAYKP와 CAPCAK의 최장 공통 문자열은 CA가 된다.

---

알고리즘 설명

문자열을 하나씩 비교하여
1. 문자가 같은경우 LCS[i][j]=LCS[i-1][j-1]
2. 문자가 다른경우 왼쪽와 위쪽의 값 중 더 큰 값 LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1])
을 선택한다.
알고리즘으로 ACAYKP와 CAPCAK를 비교하면 아래와 같은 표가 생긴다.

문자가 같은경우 LCS[i][j]=LCS[i-1][j-1] 인 이유

선택된 부분을 보면 AC와 CAPC를 비교하는 과정에 있다.
C는 공통된 부분이니, A와 CAP를 비교한 값 +1을 해준것이다.

문자가 다른경우 왼쪽와 위쪽의 값 중 더 큰 값 LCS[i][j]=max(LCS[i-1][j],LCS[i][j-1]) 이유

선택된 부분을 보면 ACA와 CAP를 비교하는 과정에 있다.
LCS[i-1][j]와 LCS[i][j-1]의 의미는 AC와 CAP, ACA와 CA를 비교하는 것과 같은 의미이다.
AC와 CAP, ACA와 CA는 각각 문자열(A또는 P)가 추가되기전 비교값이므로 이전값에 해당한다.
따라서 그 두 값중 큰 값이 LCS[i][j]가 된다.

---

실제 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>

using namespace std;
#define endl "\n"


#define MAX 1000+1
string str1, str2;
int lcs[MAX][MAX];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	ifstream cin; cin.open("input.txt");

	cin >> str1 >> str2;

	for (int i = 1; i <= str1.length(); i++)
	{
		for (int j = 1; j <= str2.length(); j++)
		{
        	// 실제 string 인덱스는 0부터 시작이지만 i,j는 1부터 시작이므로 맞춰주기위해 i-1 j-1을 대입
			if (str1[i-1]==str2[j-1]) 
			{
				lcs[i][j] = lcs[i - 1][j - 1] + 1;
			}
			else {
				lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
			}
		}
	}
	
	cout << lcs[str1.length()][str2.length()];
}

---

참고

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence
https://chanhuiseok.github.io/posts/algo-34/