POJ 2406 - Power Strings, using KMP

kmp_power_string.cpp

/* Solving POJ 2406 Power Strings */
#include <iostream>
#include <cstring>

using namespace std;

class KMP_algorithm {
    public:
        int find_base(const char* pattern) {
            /* 
               next array of power string should meet 
               either of following requirements:
               - next[i]= 0
               - next[i] = next[i-1]+1
               - next[i] = next[i-1]
            */
            int sz = strlen(pattern), j = 0, i = 1;
            bool break_flag = 0;
            int *next = new int[sz+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;
                    if (next[i] == 0
                            || next[i] == next[i-1]
                            || next[i] == next[i-1]+1)
                        continue;
                    else {
                        break_flag = 1;
                        break;
                    }
                }
                else {
                    j = next[j];
                }
            }
            int last = next[sz];
            delete[] next;
            if (break_flag || (sz % (sz - last)) != 0)
                return 1;
            else return sz / (sz - last);
        }
};

char input[1000005];
int main() {
    KMP_algorithm kmp;
    while (scanf("%s", input)==1) {
        if (strcmp(input, ".") == 0) break;
        cout << kmp.find_base(input) << endl;
    }
    return 0;
}