【2018/08/22测试T1】【SDOJ 2819】string

【题目】

题目描述：

给定两个字符串 s , t，其中 s 只包含小写字母以及 *，t 只包含小写字母。
你可以进行任意多次操作，每次选择 s 中的一个 *，将它修改为任意多个（可以是 0 个）它的前一个字符。问是否能将 s 修改为 t。
有多组数据。

输入格式：

第一行一个整数 T 表示数据组数。 
每组数据两行，第一行一个字符串 s，第二行一个字符串 t。 

输出格式：

每组数据输出一行，如果能将 s 修改为 t，输出 Yes，否则输出 No。 

样例数据：

输入

2
a*
aaaa
a*
ab

输出

Yes
No

备注：

【数据范围】 
对于 20% 的数据，| s | , | t | ≤ 7。 
对于 60% 的数据，| s | , | t | ≤ 300。 
对于 100% 的数据，T ≤ 100，| s | , | t | ≤ 30000。

 

【分析】

将 s 和 t 划分为若干个极长段，满足每段以字母开头且段内只有一种字母。显然这些段是一一对应的，对于 s 中每一段，如果有 *，那么它可以变为字母个数 ≥ 它的全字母段。 时间复杂度 O( T ( | s | + | t | ) ) 

 

【代码】

先发一下我写的丑代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
int lengthA[N],lengthB[N];
char a[N],b[N],A[N],B[N];
bool flagA[N];
int main()
{
//	freopen("string.in","r",stdin);
//	freopen("string.out","w",stdout);
	int n,m,i,j,t,kA,kB;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s%s",A+1,B+1);
		n=strlen(A+1),m=strlen(B+1);
		kA=1,lengthA[1]=1,A[n+1]='#';
		memset(flagA,false,sizeof(flagA));
		for(i=2;i<=n+1;++i)
		{
			if(A[i]==A[i-1])
			  lengthA[kA]++;
			else  if(A[i]=='*')
			{
				flagA[kA]=true;
				A[i]=A[i-1];
			}
			else
			{
				a[kA]=A[i-1];
				lengthA[++kA]=1;
			}
		}
		kB=1,lengthB[1]=1,B[m+1]='#';
		for(i=2;i<=m+1;++i)
		{
			if(B[i]==B[i-1])
			  lengthB[kB]++;
			else
			{
				b[kB]=B[i-1];
				lengthB[++kB]=1;
			}
		}
		if(kA!=kB)  {printf("No\n");goto end;}
		for(i=1;i<kA;++i)
		{
			if(a[i]!=b[i])  {printf("No\n");goto end;}
			if(a[i]==b[i]&&flagA[i]&&lengthA[i]>lengthB[i])  {printf("No\n");goto end;}
			if(a[i]==b[i]&&!flagA[i]&&lengthA[i]!=lengthB[i])  {printf("No\n");goto end;}
		}
		printf("Yes\n");
		end:;
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

然后是题解的代码（简洁得多）：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 30005
using namespace std;
int T,n,m;
char s[N],t[N];
int main()
{
//	freopen("string.in","r",stdin);
//	freopen("string.out","w",stdout);
	int i,j,k,l,u;
	scanf("%d",&T);   
	while(T--)
	{
		scanf("%s%s",&s,&t);
		n=strlen(s);
		m=strlen(t);
		for(i=j=0;i<n;i=k,j=l)
		{
			u=0;
			for(k=i;k<n&&(s[k]=='*'||s[k]==s[i]);k++)
			    if(s[k]=='*')
				u++;
			for(l=j;l<m&&t[l]==t[j];l++);
			    if(!(s[i]==t[j]&&k-i-u<=l-j&&(u||k-i==l-j)))
				break;
        }
		if(i<n||j<m)  printf("No\n");
		else  printf("Yes\n");
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}