1 #include<iostream>  2 #include<cstring> 3 #include<string> 4 using namespace std; 5  6 const int maxn = 1000000 + 5; 7  8 int next[10002], n, m; 9 char text[maxn], pattern[10002];10 11 void get_next()12 {13     int i, j;14     i = -1;15     j = 0;16     ::next[0] = -1;17     while (j<m)18     {19         if (i == -1 || pattern[i] == pattern[j])20         {21             ::next[++j] = ++i;22         }23         else24             i = ::next[i];25     }26 }27 28 int KMP()29 {30     int i, j, count = 0;31     i = j = 0;32     get_next();33     while (i<n)34     {35         if (j == -1 || text[i] == pattern[j])36         {37             i++;38             j++;39             if (j == m)  count++;40         }41         else42             j = ::next[j];43     }44     return count;45 }46 47 int main()48 {49     //freopen("D:\\txt.txt", "r", stdin);50     int t, ans;51     cin >> t;52     getchar();53     while (t--)54     {55         scanf("%s", pattern);56         scanf("%s", text);57         n = strlen(text);58         m = strlen(pattern);59         ans = KMP();60         cout << ans << endl;61     }62     return 0;63 }