P57 Oulipo

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

int text[1000000], pattern[10000];
int nextTable[10000];

void getNextTable(string pattern){
    int m = pattern.size();
    int j = 0;
    nextTable[j] = -1;
    int i = nextTable[j];
    while(j < m){
        if(i == -1 || pattern[i] == pattern[j]){
            i++;
            j++;
            nextTable[j] = i;
        }else{
            i = nextTable[i];
        }
    }
} 

int KMP(string text, string pattern){
    getNextTable(pattern);
    int n = text.size();
    int m = pattern.size();
    int i = 0;
    int j = 0;
    int number = 0;
    while(i < n){
        if(j == -1 || text[i] == pattern[j]){
            i++;
            j++;
        }else{
            j = nextTable[j];
        }
        if(j == m){
            number++;        
            j = nextTable[j];    
        }    
    }
    return number;
}

int main(){
    int t;
    string pattern, text;
    cin >> t;

    while(t--){
        cin >> pattern >> text;

        printf("%d\n", KMP(text,pattern));
    }

    return 0;
}