POJ-3461 Oulipo KMP

 1 //STATUS:C++_AC_94MS_1240KB

 2 #include<stdio.h>

 3 #include<stdlib.h>

 4 #include<string.h>

 5 #include<math.h>

 6 #include<iostream>

 7 #include<string>

 8 #include<algorithm>

 9 #include<vector>

10 #include<queue>

11 #include<stack>

12 #include<map>

13 using namespace std;

14 #define LL long long

15 #define pii pair<int,int>

16 #define Max(a,b) ((a)>(b)?(a):(b))

17 #define Min(a,b) ((a)<(b)?(a):(b))

18 #define mem(a,b) memset(a,b,sizeof(a))

19 #define lson l,mid,rt<<1

20 #define rson mid+1,r,rt<<1|1

21 #define PI acos(-1.0)

22 const int N=10010,INF=0x3f3f3f3f,MOD=10000,STA=8000010;

23 const LL LNF=0x3f3f3f3f3f3f3f3f;

24 const double DNF=1e13;

25 //

26 void swap(int& a,int& b){int t=a;a=b;b=t;}

27 void swap(LL& a,LL& b){LL t=a;a=b;b=t;}

28 //

29 

30 char s[N*100],te[N];

31 int next[N];

32 int T;

33 

34 void getnext(char *s)

35 {

36     int j=0,k=-1,len=strlen(s);

37     next[0]=-1;

38     while(j<len){

39         if(k==-1 || s[j]==s[k])

40             next[++j]=++k;

41         else k=next[k];

42     }

43 }

44 

45 int main()

46 {

47  //   freopen("in.txt","r",stdin);

48     int i,j,lent,lens,ans;

49     scanf("%d",&T);

50     while(T--)

51     {

52         ans=0;

53         scanf("%s%s",te,s);

54         lent=strlen(te);

55         lens=strlen(s);

56         getnext(te);

57 

58         for(i=j=0;i<lens;i++){

59             while(s[i]!=te[j] && j!=-1)j=next[j];

60             j++;

61             if(j==lent){j=next[j];ans++;}

62         }

63 

64         printf("%d
",ans);

65     }

66     return 0;

67 }