算法入门-最长公共子序列

牛可乐和最长公共子序列

https://ac.nowcoder.com/acm/problem/235624

题意

给定两个字符串a,b,求a,b最长公共子串

思路

  • 动态规划,最长的子串一定是由倒数第二长的子串加上两个串中一组相同的字符得来的
  • 即:(相同时) (不同)

AC代码

#include<bits/stdc++.h>
using namespace std;
int f[5050][5050];
int main(){
    string a,b;
    while(cin >> a >> b){
        a=' '+a;
        b=' '+b;
        if(a[1]==b[1]) f[1][1]=1;
        for(int i=1;i<a.size();i++){
            for(int j=1;j<b.size();j++){
                if(a[i]==b[j])f[i][j]=1+f[i-1][j-1];
                else f[i][j]=max(f[i-1][j],f[i][j-1]);
            }
        }
        cout << f[a.size()-1][b.size()-1] << endl;    
    }
    return 0;
    
}

全部评论

相关推荐

点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务