NY10A SPOJ

NY10A.cpp

#include <bits/stdc++.h>

#define _for(i,a,b) for(int i=(a),_b_=(b),_d_=(a<b?1:-1);i!=_b_;i+=_d_)
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define _it(i,v) for (typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define _all(v) v.begin(), v.end()

#define DEBUG(x) { cout << #x << " = " << x << endl; }
#define sqr(x) ((x)*(x))
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int cntKMP(string s, string t) {
    int n = s.length(), m = t.length();
    int cnt = 0;
    int* pit = new int[m+1];
    if(m >= 0) pit[0] = 0;    
    if(m >= 1) pit[1] = 0;
    FOR(i, 2, m) { 
        for(int j = pit[i-1]; ;j = pit[j]) {
            if(t[j] == t[i-1]) { pit[i] = j + 1; break; }
            if(j == 0) { pit[i] = 0; break; }
        }
    }
        for(int i = 0, j = 0; i < n; ) {
        if(s[i] == t[j]) {
            i++; j++;
            if(j == m) cnt++;
        } else if(j > 0) {
            j = pit[j];
        } else i++;
    } delete[] pit;
    return cnt;
}
// end KMP algorithm

// TTT, TTH, THT, THH, HTT, HTH, HHT and HHH.

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #ifndef ONLINE_JUDGE
        freopen("INPUT.inp", "r", stdin);
    #endif

    // solution starts...
    string s;
    int test, a;
    cin >> test;
    while(test--) {
        cin >> a >> s;
        cout << a << ' ' << cntKMP(s, "TTT") 
                  << ' ' << cntKMP(s, "TTH") 
                  << ' ' << cntKMP(s, "THT") 
                  << ' ' << cntKMP(s, "THH") 
                  << ' ' << cntKMP(s, "HTT") 
                  << ' ' << cntKMP(s, "HTH") 
                  << ' ' << cntKMP(s, "HHT") 
                  << ' ' << cntKMP(s, "HHH") 
                  << endl;
    }

    // solution ends...

    return 0;
}