Longest Common Substring

https://www.geeksforgeeks.org/longest-common-substring-dp-29/

두 개의 문자열 'X'와 'Y'가 주어진다면, 가장 긴 공통 substring의 길이를 찾아라.

예시
Input : X = "GeeksforGeeks", y = "GeeksQuiz"
Output : 5
The longest common substring is "Geeks" and is of
length 5.

Input : X = "abcdxyz", y = "xyzabcd"
Output : 4
The longest common substring is "abcd" and is of
length 4.

Input : X = "zxabcdezy", y = "yzabcdezx"
Output : 6
The longest common substring is "abcdez" and is of
length 6.

m과 n이 각각 첫 번째와 두 번째의 문자열의 길이라고 하자.

간단한 해결책은, 첫 번째 string의 모든 substrings을 모든 substring에 대해 하나씩 고려하는 것이고, second string에 있는 substring인지 체크하는 것이다. maximum length subsring을 추적한다. O(m^2) substrings이 있을 것이고, 우리는 한 string이 또 다른 string에 있는 substring인지를 O(n 시간에 찾을 수 있다. 그래서 이 방법의 전체 시간 복잡도는 O(n * m^2) 이다.

Dynamic Programming은 O(m*n) 시간에 longest common substring을 찾는데 사용될 수 있다. 그 아이디어는 두 문자열의 모든 subsrings에 대해 longest common suffix의 길이를 찾고, 이러한 길이를 한 테이블에 저장하는 것이다.

longest common suffix는 다음의 최적의 substructure property를 갖는다.
LCSuff(X, Y, m, n) = LCSuff(X, Y, m - 1, n -1) + 1 if (X[m-1] == Y[n-1])
                          0 Otherwise (if X[m-1] != Y[n-1])
maximum length Longest Common Suffix는 longest common substring이다.
LCSubStr = Max(LCSuff(X, Y, i, j)) where 1 <= i <=m
                                                     1<= j <= n
다음은 위의 솔루션의 iterative 구현이다.