POJ 3461

#define ll long long
#include <iostream>
#include <vector>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

vector<int> computePrefixes(string s) {
    vector<int> ret(s.length());
    ret[0] = 0;
    for(int i = 1, k = 0; i < s.length(); i++) {
        //cout << "i = " << i << " k = " << k << "\n";
        while(k > 0 && s[i] != s[k]) {
            k = ret[k-1];
        }
        if(s[i] == s[k]) {
            ret[i] = ++k;
        }
        else {
            ret[i] = k;
        }
        //cout << "ret[" << i << "] is " << ret[i] << "\n";
    }
    return ret;
}

int kmp(string W, string T) {
    vector<int> pre = computePrefixes(W);
    //cout << "pre is ";
    //cout << "\n";
    int ans = 0;
    for(int i = 0, k = 0; i < T.length(); i++) {
        //cout << " i = " << i << " k = " << k << "\n";
        while(k > 0 && T[i] != W[k]) {
            k = pre[k-1];
        }
        if(T[i] == W[k]) {
            k++;
        }
        if(k == W.length()) {
            ans++;
            k = pre[k-1];
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    string in;
    getline(cin,in);
    while(t--) {
        string W,T;
        getline(cin,W);
        getline(cin,T);
        cout << kmp(W,T) << "\n";
    }
    return 0;
}