Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

此题其实是求最长公共子串

Posted by lzxzy at 2018-08-18 14:44:34 on Problem 1936 and last updated at 2018-08-18 14:45:03
/*附代码*/
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator