问题：有两个字符串str和str2，求出两个字符串中最长公共子串长度。
比如：str=acbcbcef，str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串长度为5。
需要注意的就是 最长公共子串（Longest Common Substring）与 最长公共子序列（Longest Common Subsequence）的区别： 子串要求在原字符串中是连续的，而子序列则只需保持相对顺序，并不要求连续。
算法思路：
1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。
3、通过查找出值为1的最长对角线就能找到最长公共子串。
针对于上面的两个字符串我们可以得到的二维矩阵如下：
从上图可以看到，str1和str2共有5个公共子串，但最长的公共子串长度为5。
为了进一步优化算法的效率，我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度，即某个二维矩阵元素的值由record[i][j]=1演变为record[i][j]=1 +record[i-1][j-1]，这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下：
C++代码实现如下:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
string getLCS(string str1, string str2) { vector<vector<int> > record(str1.length(), vector<int>(str2.length())); int maxLen = 0, maxEnd = 0; for(int i=0; i<static_cast<int>(str1.length()); ++i) for (int j = 0; j < static_cast<int>(str2.length()); ++j) { if (str1[i] == str2[j]) { if (i == 0 || j == 0) { record[i][j] = 1; } else { record[i][j] = record[i - 1][j - 1] + 1; } } else { record[i][j] = 0; } if (record[i][j] > maxLen) { maxLen = record[i][j]; maxEnd = i; //若记录i,则最后获取LCS时是取str1的子串 } } return str1.substr(maxEnd - maxLen + 1, maxLen); } |