题解 | #公共子串计算#

#include<iostream>
#include<string>
#include<vector>
#include<math.h>
// 核心是需要明确dp的准确定义，dp表示以a字符串以i字符结尾时，b字符串以j字符结尾时的最大子序列长度。
using namespace std;

int main(){
    string strs1,strs2;
    getline(cin,strs1);
    getline(cin,strs2);
    int M = strs1.size(),N = strs2.size();
    int maxLen = 0;
    vector<vector<int>>dp(M+1,vector<int>(N+1,0));
    for(int i = 1;i<=M;i++)
    {
        for(int j = 1;j<=N;j++)
        {
            if(strs1[i-1] == strs2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                if(dp[i][j] > maxLen)
                {
                    maxLen = dp[i][j];
                }
            }
            else {
                dp[i][j] = 0;
            }
        }
    }
    cout << maxLen << endl;
}