4354 문자열 제곱

문자열이 주어졌을 때

특정 문자열 a의 n번 반복으로 이루어져 있다고 생각할 수 있다.

이 때 n의 최대값을 구한다.

KMP의 P배열은 x위치에서 다른글자가 나왔을 때 P[x]위치부터 확인하면 된다는 것을 의미한다

만약 문자열 맨 끝에서 P배열을 쭉 따라갔을 때 항상 일정한 간격으로 점프한다면 해당 문자열은 점프한 간격만큼의 문자열로 반복되는 것이다.

#include <stdio.h>
#define mv 1000002
 
char p[mv];
int f[mv], m;
int strlen(char *c) {
    int i = 0;
    while (c[i]) i++;
    return i;
}
 
int main() {
    while (1) {
        fgets(p, mv, stdin);
        if (p[0] == '.') break;
        m = strlen(p);
        if (p[m - 1] == '\n') p[--m] = 0;
        for (int i = 1, j = 0; i < m; i++) {
            while (j && p[i] != p[j]) j = f[j - 1];
            if (p[i] == p[j]) f[i] = ++j;
        }
        int l = m - f[m - 1];
        int temp = f[m - 1];
        while (temp - f[temp - 1] == l) {
            temp = f[temp- 1];
        }
        printf("%d\n", temp == 0 ? m / l : 1);
        for (int i = 0; i < m; i++) f[i] = 0;
    }
    return 0;
}