(UVA) 10298 - Power Strings [string matching, KMP]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=1239

Tips : KMP + features XD

#include <iostream>
#include <stdio.h>
using namespace std;

const int MAX_N = 1e6 + 6;

int fail[MAX_N];

void build(string b) {
    int len=b.size();
    int pos;
    pos = fail[0] = -1;
    for (int i=1;len > i;i++) {
        while (pos != -1 && b[pos + 1] != b[i]) {
            pos = fail[pos];
        }
        if (b[pos+1] == b[i]) pos++;
        fail[i] = pos;
    }
}

int match(string a,string b) {
    int lena=a.size(),lenb=b.size();
    int pos=-1;
    int cnt=0;
    for (int i=0;i<lena;i++) {
        while (pos != -1 && b[pos+1] != a[i]) {
            pos = fail[pos];
        }
        if (b[pos + 1] == a[i]) pos++;
        if (pos == lenb - 1) {
            cnt++;
            pos = fail[pos];
        }
    }
    return cnt;
}

int main () {
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    string s;
    while (getline(cin,s)) {
        //cout<<s<<"*\n";
        if (s==".") break;
        build(s);
        int k=s.size() - fail[s.size()-1] - 1;
        //for (int x=0;s.size()>x;x++) cout<<fail[x]<<' ';
        //cout<<endl;
        //cout<<"sz = "<<s.size()<<" , fail = "<<fail[s.size()-1]<<endl;
        if (s.size() % k ==0) printf("%d\n",s.size()/k);
        else puts("1");
    }
}