718. 最长公共子串

题目：给定两个整数数组A和B，返回两个数组中最长的公共子串的长度。
思路：注意和最长公共子序列的思想区分，子串要求连续。定义dp[i][j]表示A[i:]和B[j:]的最长公共前缀(以A[i]/B[j]为起始点的子串)的长度，如果A[i]==B[j]，则dp[i][j] = dp[i+1][j+1] + 1，否则dp[i][j] = 0，答案即为所有dp[i][j]中的最大值。

int findLength(vector<int>& A, vector<int>& B){
    int m = A.size();
    int n = B.size();
    int dp[m+1][n+1]; //dp[i][j]表示字符串A[i:]和B[j:]的最长公共前缀的长度
    for(int i=0; i<=m; i++) dp[i][n] = 0;
    for(int j=0; j<=n; j++) dp[m][j] = 0;
    int max_res = 0;

    for(int i=m-1; i>=0; i--){
        for(int j=n-1; j>=0; j--){
            if(A[i]==B[j]){
                dp[i][j] = dp[i+1][j+1]+1;
            }else{
                dp[i][j] = 0;
            }
            if(dp[i][j]>max_res) max_res = dp[i][j];
        }
    }
    return max_res;
}