LCS

LCS(longest common sequence) - 공통되는 최장 부분수열

 

string f = ACAYKP

string s = CACANK

 

이렇게 두 문자열이 있다면 공통되는 최대 길이의 부분수열은 A C A K -> 4 가 된다.

LCS 는 DP 를 통해서 구현되며

LCS4 번 문제같은 조건이 주어진 숫자의 경우 lis 알고리즘으로 해결한다.

(나중에 공부하고 포스팅해야지)

 

기본적으로 두 문자열에 대한 dp[][] 를 선언으로 시작한다.

한 문자열에 대해서 다른 문자열의 각 문자를 전부 비교한다.

 

f[i] == s[k] 이면 dp[i][k] = dp[i-1][k-1]+1;

f[i] != s[k] 이면 dp[i][k] = max(dp[i-1][k], dp[i][k-1]);

 

************************************************************************

부분수열이 아닌 문자열을 찾는 것이라면

f[i] == s[k] 이면 dp[i][k] = dp[i-1][k-1]+1;

위 점화식을 이용하여 공통된 문자열의 최대 길이를 찾을 수 있다.

ex)

ACACK

CACIP

--> CAC : 3

************************************************************************