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