Longest Common Substring

    Given two strings, find the longest common substring.

    Return the length of it.

    Notice

    The characters in substring should occur continuously in original string.
    This is different with subsequence.

    Given A = , B = "CBCE", return 2.

    Challenge **

    O(n x m) time and memory.

    Python

    C++

    1. class Solution {
    2. public:    
    3.     /**
    4.      * @param A, B: Two string.
    5.      * @return: the length of the longest common substring.
    6.      */
    7.     int longestCommonSubstring(string &A, string &B) {
    8.         if (A.empty() || B.empty()) {
    9.             return 0;
    10.         }
    12.         int lcs = 0;
    13.         for (int i = 0; i < A.length(); ++i) {
    14.             for (int j = 0; j < B.length(); ++j) {
    15.                 int lcs_temp = 0;
    16.                 while ((i + lcs_temp < A.length()) &&
    17.                        (A[i + lcs_temp] == B[j + lcs_temp])) {
    18.                     ++lcs_temp;
    19.                 }
    20.                 // update lcs
    21.                 if (lcs_temp > lcs) lcs = lcs_temp;
    22.             }
    23.         }
    25.         return lcs;
    26.     }

    源码分析

    1. 异常处理，空串时返回0.
    2. 分别使用i和j表示当前遍历的索引处。若当前字符相同时则共同往后移动一位。
    3. 没有相同字符时比较此次遍历的lcs_temp和lcs大小，更新lcs.
    4. 返回lcs.

    注意在while循环中不可直接使用++i或者++j，即两根指针依次向前移动，不能在内循环处更改，因为有可能会漏解！

    复杂度分析

    双重 for 循环，最坏时间复杂度约为 O(mn \cdot lcs), lcs 最大可为 \min{m, n} .

    题解1中使用了两根指针指向当前所取子串的起点，在实际比较过程中存在较多的重复计算，故可以考虑使用记忆化搜索或者动态规划对其进行优化。动态规划中状态的确定及其状态转移方程最为关键，如果直接以题目所求为状态，我们会发现其状态转移方程似乎写不出来，但退而求其次，我们不妨采用子串/子序列中常用的状态定义——『以(i,j)结尾(如 A[i-1], B[j-1])且其字符相等的子串lcs, 状态转移时只需判断两个字符串后一位字符是否相等，最后再次遍历二维状态数组即可。

    1. class Solution:
    2.     # @param A, B: Two string.
    3.     # @return: the length of the longest common substring.
    4.     def longestCommonSubstring(self, A, B):
    5.         if not (A and B):
    6.             return 0
    8.         n, m = len(A), len(B)
    9.         f = [[0 for i in range(m + 1)] for j in range(n + 1)]
    10.         for i in range(n):
    11.             for j in range(m):
    12.                 if A[i] == B[j]:
    13.                     f[i + 1][j + 1] = 1 + f[i][j]
    15.         lcs = max(map(max, f))
    16.         return lcs

    C++

    Java

    1. public class Solution {
    2.     /**
    3.      * @return: the length of the longest common substring.
    5.     public int longestCommonSubstring(String A, String B) {
    6.         if ((A == null || A.isEmpty()) ||
    7.             (B == null || B.isEmpty())) {
    8.             return 0;
    9.         }
    11.         int n = A.length();
    12.         int m = B.length();
    13.         int[][] f = new int[n + 1][m + 1];
    15.         for (int i = 0; i < n; i++) {
    16.             for (int j = 0; j < m; j++) {
    17.                 if (A.charAt(i) == B.charAt(j)) {
    18.                     f[i + 1][j + 1] = 1 + f[i][j];
    19.                 }
    20.             }
    21.         }
    23.         // find max lcs
    24.         int lcs = 0;
    25.         for (int i = 1; i <= n; i++) {
    26.             for (int j = 1; j <= m; j++) {
    27.                 if (f[i][j] > lcs) lcs = f[i][j];
    28.             }
    29.         }
    31.         return lcs;
    32.     }
    33. }
    1. 异常处理
    2. 列出状态转移方程，关键处在于以 (i,j) 结尾的两个字符串

    复杂度分析