正题

题目链接:http://noip.ybtoj.com.cn/contest/86/problem/2

---

题目大意

给两个字符串，第一个中的$\ast$号可以替换为若干个（可以为0个）相同的它的前一个字符。求能否构成第二个字符串。

---

解题思路

把所有的$\ast$号去掉然后在有的$\ast$号的连续相同字符后面加上一个$\ast$。然后就可以暴力判断了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=3e4+10; int T,n,m; char s[N],t[N]; int main() {freopen("strinq.in","r",stdin);freopen("strinq.out","w",stdout);scanf("%d",&T);while(T--){scanf("%s",s+1);n=strlen(s+1);scanf("%s",t+1);m=strlen(t+1);int last=0,cnt=0,tail=0;bool flag=0;for(int i=1;i<=n;i++){if(last&&(s[i]==last||s[i]=='*'))cnt+=(s[i]==last); else if(s[i]=='*')last=s[i-1],cnt=0;else if(last){for(int j=1;j<=cnt;j++)s[++tail]=last;last=0;s[++tail]='*';s[++tail]=s[i];}else s[++tail]=s[i];}if(last){for(int j=1;j<=cnt;j++)s[++tail]=last;s[++tail]='*';}n=tail;tail=1;for(int i=1;i<=n;i++){if(s[i]!='*'&&tail>m){flag=1;break;}else if(s[i]==t[tail])tail++;else if(s[i]=='*'){while(s[i]=='*'&&t[tail]==s[i-1])tail++;}else{flag=1;break;}}if(flag||tail<=m)printf("No\n");else printf("Yes\n");} }

总结

以上是生活随笔为你收集整理的YbtOJ#20060-[NOIP2020模拟赛B组Day3]字串修改【模拟】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。