| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
此题其实是求最长公共子串/*附代码*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
char x[100005],y[100005];
int len1,len2;
int f[2][100005],c;
void js()
{
c=0;
for(int i=1;i<=len2;i++)
{
c=1-c;
for(int j=1;j<=(i<len1?i:len1);j++)//优化
{
if(y[i-1]==x[j-1])f[c][j]=f[1-c][j-1]+1;
else if(f[1-c][j]>f[c][j-1])f[c][j]=f[1-c][j];
else f[c][j]=f[c][j-1];
}
}
if(f[c][len1]==len1)printf("Yes\n");
else printf("No\n");
}
int main()
{
while(scanf("%s",x)!=EOF)
{
scanf("%s",y);
len1=strlen(x);len2=strlen(y);
memset(f,0,sizeof(f));
js();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator