POJ 3461 Oulipo : using KMP to find sub strings

kmp_occurrence.cpp

/* Solving POJ 3461 Oulipo */
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class KMP_algorithm {
    private:
        vector<int> next;
        string pattern;
    public:
        void find_next(const string& p) {
            pattern = string(p);
            int sz = pattern.size(), j = 0, i = 1;
            next = vector<int>(sz+1);
            next[0] = -1;
            while (i < sz) {
                if (j == -1 || pattern[i] == pattern[j]) {
                    next[++i] = ++j;
                }
                else {
                    j = next[j];
                }
            }
        }
    
        int pattern_match(const string& source) {
            int s_len = source.size(), p_len = pattern.size();
            int si = 0, pi = 0, cnt=0; // index of source and pattern
            while (si < s_len) {
                if (pi == -1 || source[si] == pattern[pi]) {
                    ++si, ++pi;
                }
                else {
                    pi = next[pi];
                }
                if (pi == p_len) {
                    cnt++;
//                    cout << "found pattern at index " << si-pi << endl;
                    pi = next[pi];
                }
            }
            return cnt;
        }

        void print_next() {
            for (int i=0, im=next.size(); i<im; ++i)
                cout << next[i] << " ";
            cout << endl;
        }
};

int main() {
    int num;
    KMP_algorithm kmp;
    scanf("%d\n", &num);
    for (int i=0; i<num; ++i) {
        string p, s;
        getline(cin, p); 
        getline(cin, s);
        kmp.find_next(p);
        cout << kmp.pattern_match(s) << endl;  
    }
    return 0;
}