POJ 1961 - Period, using 'next' array from KMP algorithm

kmp_period.cpp

/* Solving POJ 1961 Period */
#include <iostream>
#include <cstring>

using namespace std;

char input[1000005];
int next[1000006];

class KMP_algorithm {
    public:
        void find_period(const char* pattern, int sz) {
            int 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];
                }
            }
            
            for (i=2; i<=sz; ++i) {
                if (next[i] != 0 && i % (i-next[i]) == 0) 
                    printf("%d %d\n", i, i/(i-next[i]));
            }
            cout << endl;
        }
};

int main() {
    KMP_algorithm kmp;
    int size, num = 0;
    while (scanf("%d", &size)==1) {
        if (size == 0) break;
        scanf("%s", input);
        printf("Test case #%d\n", ++num);
        kmp.find_period(input, size);
    }
    return 0;
}