「JoyOI1050」最长公共子序列

2013年12月1日3,8000

题目描述

一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad” ,顺次选1，3，5个字符就构成子串” cad” ,现给定两个字符串，求它们的最长共公子串。

输入

第一行两个字符串用空格分开。

输出

最长子串的长度。

样例输入

abccd aecd

样例输出

提示

两个串的长度均小于2000

代码

#include<iostream> 
#include<cstring> 
using namespace std; 
string x,y; 
int f[2001][2001]; 
int main() 
{ 
    cin>>x>>y; 
    int lx=x.length(),ly=y.length(); 
    x=" "+x;y=" "+y;  
    memset(f,0,sizeof(f)); 
    for(int i=1;i<=lx;i++) 
        for(int j=1;j<=ly;j++) 
        { 
            if(x[i]==y[j])f[i][j]=f[i-1][j-1]+1; 
            else f[i][j]=max(f[i-1][j],f[i][j-1]); 
        } 
    cout<<f[lx][ly]<<endl; 
    return 0; 
}

#include<iostream>

#include<cstring>

using namespace std;

string x,y;

int f[2001][2001];

int main()

{

cin>>x>>y;

int lx=x.length(),ly=y.length();

x=" "+x;y=" "+y;

memset(f,0,sizeof(f));

for(int i=1;i<=lx;i++)

for(int j=1;j<=ly;j++)

{

if(x[i]==y[j])f[i][j]=f[i-1][j-1]+1;

else f[i][j]=max(f[i-1][j],f[i][j-1]);

}

cout<<f[lx][ly]<<endl;

return 0;

}

« 「JoyOI1049」最长不下降子序列「RQNOJ106」最大加权矩形(最大子矩阵和问题) »

hzwer.com _ Home | http://hzwer.com

「JoyOI1050」最长公共子序列

题目描述

输入

输出

样例输入

样例输出

提示

代码

分类目录

热门文章

Myfriends

近期评论