题解 | #公共子串计算#

#include <iostream>

using namespace std;

int dp[200][200];

/**
 * dp[i][j]表示str1中以第i-1个字符为末尾的子串和str2中以第j-1个字符为末尾的子串的公共子串长度
 * dp[0][j] = 0,dp[i][0] = 0
 */
int maxComLen(string str1,string str2){
    int maxLen = 0;
    for (int i = 0; i <= str1.size(); ++i) {
        for (int j = 0; j <= str2.size(); ++j) {
            if (i==0 || j==0) dp[i][j] = 0;
            else if (str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = 0;
            if (maxLen < dp[i][j]) maxLen = dp[i][j];
        }
    }
    return maxLen;
}

int main(){
    string str1,str2;
    while (cin>>str1>>str2){
        cout<<maxComLen(str1,str2)<<endl;
    }
    return 0;
}