文章

150

粉丝

0

获赞

558

访问

23.2k

头像
最长连续公共子序列 题解:
P1730 西安电子科技大学/南京大学机试题
发布于2026年2月12日 18:03
阅读数 214

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

int dp[105][105];
int main(){    
    string a, b;
    while(cin >> a >> b){
        int la = a.size();
        int lb = b.size();        
        // 初始化dp数组为0
        memset(dp, 0, sizeof(dp));       
        int maxLen = 0;          // 记录最长长度
        int endPos = 0;          // 记录最长子串在a中的结束位置(用于输出)       
        for(int i = 1; i <= la; ++i){
            for(int j = 1; j <= lb; ++j){
                // 当前字符相等,连续长度+1
                if(a[i-1] == b[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;                  
                    // 更新最大值(注意:取最后一个,所以>=)
                    if(dp[i][j] >= maxLen){
                        maxLen = dp[i][j];
                        endPos = i;  // 记录在a中的结束位置
                    }
                }
                // 当前字符不相等,连续中断,长度为0
                else{
                    dp[i][j] = 0;
                }
            }
        }	      ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发