https://www.lintcode.com/problem/longest-common-substring/
X. Suffix Trie
https://stackoverflow.com/questions/11004123/how-to-find-longest-common-substring-using-trees
X. Suffix Array
https://algs4.cs.princeton.edu/63suffix/LongestCommonSubstring.java.html
X. DP
https://www.jiuzhang.com/solution/longest-common-substring/
X. - Add cache?
http://illya-keeplearning.blogspot.com/2009/06/suffix-trees-longest-common-substring.html
Given two strings, find the longest common substring.
Return the length of it.
Have you met this question in a real interview?
Example
Given A =
"ABCD", B = "CBCE", return 2.Challenge
O(n x m) time and memory.
X. Suffix Trie
https://stackoverflow.com/questions/11004123/how-to-find-longest-common-substring-using-trees
This is what I get when running "ABCDE$XABCZ" through my code.
4. 查找两个字符串 Text1 和 Text2 的最长公共部分（即Lowest Common Ancestor）
解决方案：连接 Text1+# + Text2+$ 形成新的字符串并构造后缀树，找到最深的非叶节点，且该节点的叶节点既有 # 也有 $。
另外，这个可以从两个推广到多个字符串。
查找LCA的算法是O(1)的复杂度，代价是需要对后缀树做复杂度为O(n)的预处理。
曾记得以前学过树结构的LCA各种算法，比如Tarjan算法（DFS+并查集，离线）、RMQ（时间戳，在线）、树链剖分等，年代久远，这些东西都记不清楚了T_T。
此外，还有一种二进制树检索LCA的方法，用二进制的每一位表示路径方向，0表示左儿子，1表示右儿子。只需将需要比较的两个节点的二进制值进行XOR计算，即可得知二者重叠的路径（根据XOR的定义知，左边连续的0右多少个，则有多少重叠）。将任意后缀树mapping到二进制树中，即可快速地检索出LCA。（关于二进制树，具体请参考Algorithms on Strings, Trees and Sequences 一书）
X. Suffix Array
https://algs4.cs.princeton.edu/63suffix/LongestCommonSubstring.java.html
X. DP
Time Complexity: O(m*n)
Auxiliary Space: O(m*n)
https://www.geeksforgeeks.org/longest-common-substring-dp-29/Auxiliary Space: O(m*n)
A simple solution is to one by one consider all substrings of first string and for every substring check if it is a substring in second string. Keep track of the maximum length substring. There will be O(m^2) substrings and we can find whether a string is subsring on another string in O(n) time (See this). So overall time complexity of this method would be O(n * m2)
Dynamic Programming can be used to find the longest common substring in O(m*n) time. The idea is to find length of the longest common suffix for all substrings of both strings and store these lengths in a table.
The longest common suffix has following optimal 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])
The maximum length Longest Common Suffix is the longest common substring.
LCSubStr(X, Y, m, n) = Max(LCSuff(X, Y, i, j)) where 1 <= i <= m
and 1 <= j <= n
public int longestCommonSubstring(String A, String B) {
// state: f[i][j] is the length of the longest lcs
// ended with A[i - 1] & B[j - 1] in A[0..i-1] & B[0..j-1]
int n = A.length();
int m = B.length();
int[][] f = new int[n + 1][m + 1];
// initialize: f[i][j] is 0 by default
// function: f[i][j] = f[i - 1][j - 1] + 1 or 0
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = 0;
}
}
}
// answer: max{f[i][j]}
int max = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
max = Math.max(max, f[i][j]);
}
}
return max;
}
X. - Add cache?
http://illya-keeplearning.blogspot.com/2009/06/suffix-trees-longest-common-substring.html
