BaekJoon(5582)::공통 부분 문자열

문제 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제파악 해당문제는 LCS와 비슷하게 풀 수 있는 문제이다. 다만, 기존 LCS는 Longest-Common-Subsequence라면 해당 문제는 Longest-Common-SubString 문제이다. 위 두 LCS또한 결국 DP문제이기 때문에 점화식을 통해 문제를 해결하면 쉽게 해결가능하다. 문제풀이 해당문제의 LCS(Longest Common SubString)의 점화식을 구해보면 다음과 같다. $$ LCS(X_i, Y_j) = \begin{..