1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<string> 5 #include<memory.h> 6 using namespace std; 7  8 int count = 0; 9 string s,l;10 11 void get_next(string src, int m, int *next)12 {13     int i = 0,j = -1;14     next[0] = j;15     while (i < m) {16         while (j != -1 && src[j] != src[i])17             j = next[j];18         i++,j++;19         if (j == m)20             next[i] = next[j-1];21         else next[i] = j;22     }23 }24 25 void kmp(string s,int m, string l, int n)26 {27     int next[10005];28     get_next(s,m,next);29     int i = 0,j = 0;30     while (i < n) {31         while (j != -1 && s[j] != l[i])32             j = next[j];33         i++,j++;34         if (j == m){35             count++;36             j = next[j];37         }38     }39 }40 int main()41 {42     int t;43     cin >> t;44     while (t--) {45         count = 0;46         cin >> s >> l;47         kmp(s,s.length(),l,l.length());48         cout << count << endl;49     }50     return 0;51 }