LCS(Longest Common Substring) 알고리즘

두 문자열에서 최장 공통 부분문자열(연속) 찾기

 

DP(Dynamic Programming) 이용

int dp[n][m];
int a[n];
int b[m];

if(i==0 && j==0)
	dp[i][j] = 0;
else if(a[i] == b[j])
	dp[i][j] = dp[i-1][j-1]+1;
else
	dp[i][j] = 0;

 

dp배열의 최댓값 => 최장 공통 부분문자열 길이