# Longest Common Substring ### Source - lintcode: [(79) Longest Common Substring](http://www.lintcode.com/en/problem/longest-common-substring/) ~~~ Given two strings, find the longest common substring. Return the length of it. Example Given A="ABCD", B="CBCE", return 2. Note The characters in substring should occur continuously in original string. This is different with subsequence. ~~~ ### 題解 求最長公共子串，注意「子串」和「子序列」的區別！簡單考慮可以使用兩根指針索引分別指向兩個字符串的當前遍歷位置，若遇到相等的字符時則同時向后移動一位。 ### C++ ~~~ class Solution { public: /** * @param A, B: Two string. * @return: the length of the longest common substring. */ int longestCommonSubstring(string &A, string &B) { if (A.empty() || B.empty()) { return 0; } int lcs = 0, lcs_temp = 0; for (int i = 0; i < A.size(); ++i) { for (int j = 0; j < B.size(); ++j) { lcs_temp = 0; while ((i + lcs_temp < A.size()) &&\ (j + lcs_temp < B.size()) &&\ (A[i + lcs_temp] == B[j + lcs_temp])) { ++lcs_temp; } // update lcs if (lcs_temp > lcs) { lcs = lcs_temp; } } } return lcs; } }; ~~~ ### 源碼分析 1. 異常處理，空串時返回0. 1. 分別使用`i`和`j`表示當前遍歷的索引處。若當前字符相同時則共同往后移動一位。 1. 沒有相同字符時比較此次遍歷的`lcs_temp`和`lcs`大小，更新`lcs`. 1. 返回`lcs`. 注意在`while`循環中不可直接使用`++i`或者`++j`，因為有可能會漏解！ ### 復雜度分析 雙重 for 循環，最壞時間復雜度約為 O(mn?lcs)O(mn \cdot lcs)O(mn?lcs). ### Reference - [Longest Common Substring | 九章算法](http://www.jiuzhang.com/solutions/longest-common-substring/)