c++实现
#include <iostream>
#include <string>
using namespace std;
/*
s1 = "abc"
s2 = "cabcd"
dp[i][j]
--------------------------------
---- 0 1 2 3 4
------------------------------
0 -- 0 1 0 0 0
------------------------------
1 -- 0 0 2 0 0
------------------------------
2 -- 1 0 0 3 0
--------------------------------
*/
int main() {
string s1,s2;
while(cin>>s1>>s2) {
if(s1.length()>s2.length()) {
//短的为s1，长的为s2
string t = s1;
s1 = s2;
s2 = t;
}
int dp[s1.length()][s2.length()];
for(int i=0;i<s2.length();i++) {
//dp[i][j]第一行，s1[0]和s2[i]相等就把dp[0][i]设为1，否则为0
if(s1[0] == s2[i]) {
dp[0][i] = 1;
}
else {
dp[0][i] = 0;
}
}
for(int i=0;i<s1.length();i++) {
//dp[i][j]第一列，s1[i]和s2[0]相等就把dp[i][0]设为1，否则为0
if(s1[i] == s2[0]) {
dp[i][0] = 1;
}
else {
dp[i][0] = 0;
}
}
for(int i=1;i<s1.length();i++) {
for(int j=1;j<s2.length();j++) {
if(s1[i] == s2[j]) {
dp[i][j] = dp[i-1][j-1] + 1; //关键
}
else {
dp[i][j] = 0;
}
}
}
int m = 0;
for(int i=0;i<s1.length();i++) {
for(int j=0;j<s2.length();j++) {
m = dp[i][j]>m ? dp[i][j] : m;
}
}
cout<<m<<endl;
}
}
