最长公共子串

问题描述

• 对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn，其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。
• 输入: "1AB2345CD",9,"12345EF",7
• 返回: 4
• 解释: 两个字符串都有 "2345" 子串, 并且子串在两个字符串内连续

题解思路

• 状态方程: F(i, j) 表示当A[i] == B[j] 并且把A[i]和B[j]当做是公共子串的最后一个字符所表示的最大长度, 由于是要连续的最大子串长度, 所以 F(i, j) = F(i-1, j-1) + 1;
• 初始条件
  • 初始化行: 当B[i] == A[0], F(0, i) = 1
  • 初始化列: 当A[i] == B[0], F(i, 0) = 1
• 已经有了连续子串的最大长度, 要得到最长连续子串, 根据这个最大长度所处的位置向前递推最大长度即可

代码实现

int findLongest(std::string A, int n, std::string B, int m) {
    if(n <= 0 || m <= 0) {
        return 0;
    }

    std::vector<std::vector<int>> dp(n, std::vector<int>(m, 0));
    int res = 0;

    // init row
    for(int i = 0; i < m; ++i) {
        if(A[0] == B[i]) {
            dp[0][i] = 1;
        }
    }

    for(int i = 0; i < n; ++i) {
        if(A[i] == B[0]) {
            dp[i][0] = 1;
        }
    }

    for(int i = 1; i < n; ++i) {
        for(int j = 1; j < m; ++j) {
            if(A[i] == B[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                res = std::max(res, dp[i][j]);
            }
        }
    }

    return res;
}