首页 > 其他 > 详细

LintCode 79 · 最长公共子串

时间:2021-04-15 09:31:52      阅读:18      评论:0      收藏:0      [点我收藏+]

状态表示:

\(f(i,j)\):以\(s_1[i]\)\(s_2[j]\)为结尾的两个子串\(s_1[0 \sim i]\)\(s_2[0 \sim j]\),它们的公共子串的长度。

遍历所有的\(i,j\),其中最大的\(f(i,j)\)就是答案。

状态转移:

\[\begin{cases} f(i,j) = 0 & s_1[i] \ne s_2[j] \f(i,j) = f(i-1,j-1)+1 & s_1[i] = s_2[j] \end{cases} \]

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    static const int N=1010;
    int f[N][N];
    int longestCommonSubstring(string &A, string &B) {
        // write your code here
        int n=A.size(),m=B.size();

        int res=0;
        memset(f,0,sizeof f);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(A[i-1] == B[j-1])
                {
                    f[i][j]=f[i-1][j-1]+1;
                    res=max(res,f[i][j]);
                }
                    
        return res;
    }
};

LintCode 79 · 最长公共子串

原文:https://www.cnblogs.com/fxh0707/p/14660517.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!