文章

85

粉丝

0

获赞

554

访问

11.7k

头像
最长连续公共子序列 题解:dp解法 查找连续子串
P1730 西安电子科技大学/南京大学机试题
发布于2026年3月8日 18:53
阅读数 182

#include <bits/stdc++.h>
using namespace std;

int main () {
    string s;
    while (getline(cin, s)) {
        int pos = s.find(' ');
        string s1 = s.substr(0, pos);
        string s2 = s.substr(pos + 1);
        int len1 = s1.length();
        int len2 = s2.length();
        int num_min = min(len1, len2);

        int max_len =0;
        int end_pos =0;

        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1[i-1] == s2[j-1]) {
                    dp[i][j] = dp[i-1][j-1]+1;
                    if (dp[i][j] >= max_len) {
                        end_pos = i-1;
                        max_len = dp[i][j];
                    }
                }
                else {
                    dp[i][j] = 0;
                }
            }
        }

        if (max_len == 0) {
            cout <...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发