1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4  5 using namespace std; 6  7 const int maxn1 = 10000 + 10; 8 const int maxn2 = 1000000 + 10; 9 char W[maxn1], T[maxn2];10 int next[maxn1];11 12 void get_next(char* W, int l)13 {14     int k = -1, j = 0;15     next[0] = -1;16     while(j < l)17     {18         if(k == -1 || W[k] == W[j])19         {20             ++k;21             ++j;22             next[j] = k;23         }24         else k = next[k];25     }26 }27 28 int KMP(char* W, int lenw, char* T, int lent)29 {30     int i = 0, j = 0, ans = 0;31     while(i < lent)32     {33         if(j == -1 || T[i] == W[j])34         {35             ++i;36             ++j;37         }38         else j = next[j];39         if(j == lenw)40         {41             ans++;42             j = next[j];43         }44     }45     return ans;46 }47 48 int main()49 {50     //freopen("in.txt", "r", stdin);51     int kase;52     scanf("%d", &kase);53     while(kase--)54     {55         memset(next, 0, sizeof(next));56         scanf("%s%s", W, T);57         int lenw = strlen(W);58         int lent = strlen(T);59         get_next(W, lenw);60         printf("%d\n", KMP(W, lenw, T, lent));61     }62 63     return 0;64 }