(UVA) 455 - Periodic Strings

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

one problem similar to the last one!

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

const int MAX_N = 86;

int f[MAX_N];

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

int main () {
    int T;
    cin >> T;
    int cases=0;
    while (T--) {
        if (cases) puts("");
        ++cases;
        string s;
        cin >> s;
        build(s);
        int len=s.size();
        if (len % (len - f[len-1] - 1) == 0) printf("%d\n",len - f[len-1] - 1);
        else printf("%d\n",len);
    }
}