题解 | #公共子串计算#

#include<iostream>
using namespace std;
//动态规划求解前i,j个字符的公共子串长度
int longgest_str(string a,string b){
    int m=a.size();
    int n=b.size();
    int dp[m+1][n+1];
    int maxn=0;
    for(int i=0;i<m;i++){
        dp[i][0]=0;
    }
    for(int j=0;j<n;j++){
        dp[0][j]=0;
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(a[i-1]==b[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else{
                dp[i][j]=0;
            }
            maxn=max(maxn,dp[i][j]);
        }
    }
    return maxn;
}
int main(){
    string s1,s2;
    while(cin>>s1>>s2){
        cout<<longgest_str(s1, s2)<<endl;
    }
    return 0;
}