ZOJ Problem Set - 3643 Keep Deleting

时间:2023-03-08 19:58:39
ZOJ Problem Set - 3643  Keep Deleting

题目大意

给出a和b串,a是b串的子串,如果b串有连续的a串,那么就将b串的a串删除,问删除多少次;

题目分析:

打比赛的时候没敲出来,后来想到用栈的思想去模拟就行,网上还有用KMP+栈去做的,没有KMP,也能AC,一会去学习一下KMP算法

 #include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define INF
#define maxn
using namespace std;
char a[],b[],c[];
int main()
{ while(scanf("%s %s",a,b)!=EOF)
{
int len_a=strlen(a);
int len_b=strlen(b);
int fro=,ed=;
int sum=;
for(int i=len_b-; i>=; i--)
{
c[fro++]=b[i];
if(fro<len_a) continue;
int j,t;
for(j=fro-,t=; j>=&&t<len_a; j--,t++)
{
if(c[j]!=a[t])
break;
}
if(t==len_a)
{
sum++;
fro=fro-len_a;
} }
printf("%d\n",sum);
}
return ;
}