4354-문자열 제곱

4354-문자열 제곱

정말 오랫동안 고민하다가 생각이 안 나서 결국 풀이를 흘깃 쳐다본 문제이다. 정답은 허탈하리만큼 간단했다. 그냥 실패함수를 구한 다음에, 특정한 공식에 대입만 하면 그게 답이다. 그 공식이라는 것도 복잡하지 않다. 

 

이렇게 생겼다. len은 문자열의 길이이고 fail[len-1]은 마지막 글자의 실패함수 값이다. 위의 분수 값이 정수여야만(분자가 분모로 나누어 떨어져야만) 정답으로 유효하고, 그렇지 않다면 답은 1이다. 다만 아직은 직감적으로 와닿지는 않는다. 이런 문제일수록 처음에 풀었을 때 이해를 제대로 하고 넘어가야지 다음에 비슷한 유형의 문제를 만났을 때 풀 수 있다. 현재까지 분석한 지점은 은 ptn의 길이를 의미한다(답으로서 유효한 경우에만). 이 문제는 ptn이 총 몇 번 반복될 수 있는지를 묻고 있으므로 답은 전체 문자열의 길이를 ptn의 길이로 나누어야한다는 것이다.

 

#include<stdio.h>
#include<string.h>
#define SIZE 1000009
int main() {
    while (1) {
        char txt[SIZE];    scanf("%s", txt);
        if (strcmp(txt, ".") == 0) break;
 
        int len = 0, fail[SIZE] = { 0 };
        for (; txt[len]; len++);
        for (int i = 1, j = 0; i < len; i++) {
            while (j > 0 && txt[i] != txt[j]) j = fail[j - 1];
            if (txt[i] == txt[j]) fail[i] = ++j;
        }
 
        int ans;
        if (len % (len - fail[len - 1]) == 0)
            ans = len / (len - fail[len - 1]);
        else ans = 1;
 
        printf("%d\n", ans);
    }
    return 0;
}