1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 int N, fail[2000000], ANS[2000000]; 9 char pat[2000000], text[2000000];10 inline void KMP() {11 int n = strlen(pat);12 for (int i = 0; i <= n + 1; i++) fail[i] = 0;13 for (int i = 1; i <= n - 1; i++) {14 int j = i;15 while (j>0) {16 j = fail[j];17 if (pat[j] == pat[i]) {18 fail[i + 1] = j + 1;19 break;20 }21 }22 }23 ANS[0] = 0;24 int m = strlen(text);25 for (int i = 0, j = 0; i <= m - 1; i++) {26 if (j <= n - 1 && text[i] == pat[j]) j++;27 else {28 while (j > 0) {29 j = fail[j];30 if (text[i] == pat[j]) {31 j++; break;32 }33 }34 }35 if (j == n) ANS[++ANS[0]] = i - n + 1;36 }37 }38 int main() {39 scanf("%d", &N);40 while (N--) {41 cin >> pat >> text;42 KMP();43 printf("%d\n", ANS[0]);44 }45 return 0;46 }