POJ 2752 - Seek the Name, Seek the Fame : understand next[sz] from KMP

kmp_cat_name.cpp

/* Solving POJ 2752 Seek the Name, Seek the Fame */
#include <iostream>
#include <cstring>

using namespace std;

char input[400005];
int next[400006];
int q[200003];

class KMP_algorithm {
    public:
        void seek_fame(const char* pattern) {
            int sz = strlen(pattern), j = 0, i = 1;
            for (int i=1; i<sz+1; i++) next[i] = 0;
            next[0] = -1;
            while (i < sz) {
                if (j == -1 || pattern[i] == pattern[j]) {
                    next[++i] = ++j;
                }
                else {
                    j = next[j];
                }
            }
            
            q[0] = sz; // queue
            i = next[sz], j = 1; // j records q's back
            while (i!=0) {
                q[j++] = i;
                i = next[i];
            }
            for (j -= 1; j>=0 ; --j) // output
                printf("%d ", q[j]);
            cout << endl;
        }
};

int main() {
    KMP_algorithm kmp;
    int num = 0;
    while (scanf("%s", input)==1) {
        kmp.seek_fame(input);
    }
    return 0;
}