学步园

Description

Input

Output

Sample Input

sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter

Sample Output

Yes
No
Yes
No

/* Author yan
 * POJ 1936
 * All in all
*/
#include<stdio.h>
#define MAX 100000
char str1[MAX],str2[MAX];

int main()
{
	int i,j;
	int len1,len2;
	//freopen("input","r",stdin);
	while(scanf("%s %s",str1,str2)!=EOF)
	{
		len1=strlen(str1);
		len2=strlen(str2);
		j=0;
		for(i=0;i<len2;i++)
		{
			if(str2[i]==str1[j]) j++;
		}
		if(j==len1) printf("Yes/n");
		else printf("No/n");
	}
	return 0;
}

LCS  AC!!!!

刚刚开始用循环数组时低维不应该循环，因为低维的以后会用到，因为是两层循环！！标记！！！

/* Author yan
 * POJ 1936
 * All in all
*/
#include<stdio.h>
#define MAX 100000
int opt[2][MAX];
char str1[MAX],str2[MAX];

int main()
{
	int i,j;
	int len1,len2;
	//freopen("input","r",stdin);
	while(scanf("%s %s",str1,str2)!=EOF)
	{
		len1=strlen(str1);
		len2=strlen(str2);
		memset(opt,0,sizeof(opt));
		for(i=1;i<=len1;i++)
			for(j=1;j<=len2;j++)
			{
				if(str1[i-1]==str2[j-1]) opt[i%2][j]=opt[(i-1)%2][j-1]+1;
				else if(opt[i%2][j-1]>=opt[(i-1)%2][j]) opt[i%2][j]=opt[i%2][j-1];
				else opt[i%2][j]=opt[(i-1)%2][j];
			}
		if(opt[len1%2][len2]==len1) printf("Yes/n");
		else printf("No/n");
	}
	return 0;
}