ZOJ Problem Set

题目大意：

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

题目分析：

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

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define INF
 7 #define maxn
 8 using namespace std;
 9 char a[1000],b[1000000],c[1000000];
10 int main()
11 {
12 
13     while(scanf("%s %s",a,b)!=EOF)
14     {
15         int len_a=strlen(a);
16         int len_b=strlen(b);
17         int fro=0,ed=0;
18         int sum=0;
19         for(int i=len_b-1; i>=0; i--)
20         {
21             c[fro++]=b[i];
22             if(fro<len_a) continue;
23             int j,t;
24             for(j=fro-1,t=0; j>=0&&t<len_a; j--,t++)
25             {
26                 if(c[j]!=a[t])
27                     break;
28             }
29             if(t==len_a)
30             {
31                 sum++;
32                 fro=fro-len_a;
33             }
34 
35         }
36         printf("%d
",sum);
37     }
38     return 0;
39 }