题解 | #公共子串计算#

#include <iostream>
#include <vector>
#include <string>
using namespace std;
/*
解题思路：相当于将单序列回文串变成双序列相同公共子串问题，子串不是子序列
与合唱队问题区分开，子串必须连续，子序列可以不连续
状态转移方程一样的思路:
dp[i][j]表示串1的前i位与串2的前j位是否相同
s[i-1] == s[j-1] 则dp[i][j] = dp[i-1][j-1] + 1;
s[i-1] != s[j-1] 则dp[i][j] = 0
最大公共子串长度每次比较一次，从每次比较结果中选出最长公共子串
(不同于子序列不连续时dp[i][j]不会为0，最后输出dp[m][n]即为最长子序列)
*/
int main() {
    string s1,s2;
    while(cin >> s1 >> s2){
        int m = s1.length();
        int n = s2.length();
        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(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = 0;
                maxlen = max(maxlen,dp[i][j]);
            }
        }
        cout << maxlen << endl;
    }
}
// 64 位输出请用 printf("%lld")