文章

74

粉丝

0

获赞

94

访问

8.2k

头像
最长连续公共子序列(dp解法) 题解:
P1730 西安电子科技大学/南京大学机试题
发布于2025年8月19日 14:49
阅读数 84

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;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发