欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-02-24 23:54:40
...

【题目】

题目描述:

给定两个字符串 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;
}

 

相关标签: 模拟