文章
74
粉丝
0
获赞
94
访问
8.2k
dp[i][j]表示以a[i]和b[i]结尾的最长连续公共子序列长度,要求a[i]与b[i]必须为最长连续公共子序列的结尾,否则dp=0
#include<bits/stdc++.h>
using namespace std;
int dp[1000 + 5][1000 + 5];
int main(){
string a, b;
while(cin >> a >> b){
int lena = a.size();
int lenb = b.size();
int maxx = 0;
int enda, endb;
for(int i = 1; i <= lena; i ++){
for(int j = 1; j <= lenb; j ++){
if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = 0;
if(maxx <= dp[i][j]){
enda = i-1;
endb = j-1;
maxx = dp[i][j];
}
}
}
cout << maxx << endl;
while(maxx --) cout << a[enda - maxx];
cout << endl;
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发