题解 | 最长公共子串

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        // write code here
        //动态规划，dp[i][j]代表以A[i-1]和B[j-1]作为结尾的公共子串长度
        //dp[i][j]=dp[i-1][j-1]+1, 当A[i-1]和B[j-1]相等时
        //dp[i][j]=0,当不相等时
        //只用到左上的记录，我们用一个额外位置记录即可
        vector<int>dp(m+1,0);
        int maxlen=0;//记录dp中的最大值
        for(int i=1; i<=n; i++)
        {
            //从头开始记录左上
            int prev=dp[0];
            for(int j=1; j<=m; j++)
            {
                int tmp=dp[j];//暂存修改前的dp值
                if(A[i-1]==B[j-1])
                {   
                    dp[j]=prev+1;
                    maxlen=max(maxlen,dp[j]);
                }
                else
                    dp[j]=0;
                prev=tmp;//左上的记录右移一位
            }
        }
        return maxlen;
    }
};