4354번: 문자열 제곱

https://www.acmicpc.net/problem/4354


$O(tl)$

failure function을 구현

#include<cstdio>
char s[1000001];
int f[1000001], i, j;
int main() {
    while (scanf("%s", s) && s[0] ^ '.') {
        for (f[i = 0] = j = -1; s[i]; ) j < 0 | s[j] == s[i] ? f[++i] = ++j : j = f[j];
        printf("%d\n", i % (i - f[i]) ? 1 : i / (i - f[i]));
    }
    return 0;
}