Longest Common Substring LCS(Longest Common Substring)은 두 문자열이 있을 때, 두 문자열의 최장 공통 부분 수열(공통되는 문자열 중, 최대 길이의 문자열)을 구하는 문제이다. 예를 들어 두 문자열 ACAYKP와 CAPCAK의 LCS는 ACAYKP, CAPCAK => ACAK임을 알 수 있다. 이는 간단한 dp로 풀 수 있는데, 두 문자열 a, b에 대하여 항 $dp[i][j]$를 '첫 번째 문자열 a의 구간 [ i, 끝 ], 두 번째 문자열 b의 구간 [ j, 끝 ]에 속하는 LCS 길이'라고 정의하면 i) a[i]와 b[j]가 같을 때: $dp(i, j)=dp(i+1, j+1)+1$ii) 같지 않을 때: $dp(i, j)=max( dp(i+1, j), d..
