1787-문자열의 주기 예측

1787-문자열의 주기 예측

KMP알고리즘의 실패함수를 활용하는 문제이다. 다만 실패함수를 그대로 사용하는게 아니라 약간의 변형이 필요한데, 이를 위해선 실패함수의 의미에 대해서 정확히 파악해야만 한다.

예를 들어 "bbabbab"라는 문자열이 있다고 하자. 이를 실패함수로 표현해보면,

0	1	2	3	4	5	6
b	b	a	b	b	a	b
0	1	0	1	2	3	4

가 된다. 여기서 실패함수의 값이 의미하는 바를 한번 생각해보자. 예를 들어 3번째 인덱스('b')가 의미하는 '1'은 무슨 의미일까? 해당 인덱스에서 txt와 비교를 했는데 만약 일치하지 않았다면 다음으로 비교할 지점은 ptn의 '1'번째 부터 보면 된다는 의미이다. 이것이 실패함수의 표면적인 정의이다. 하지만 이것 말고도 숨겨진 의미가 있다. 그것은 바로 txt와 ptn이 '1-1(=0)'번째 문자까지는 일치했다는 의미이다. 조금 더 일반화시키면 i번째 인덱스의 실패함수 값이 k라면, txt와 ptn은 'k-1'번째 문자까지는 일치했음이 보장된다는 소리이다. 그렇다면 이 개념을 어떻게 문제에 적용시킬 수 있을까? 다시 위의 예시로, 2번째 인덱스까지의 문자열 "bba"를 생각해보자. "bba"로 예측할 수 있는 주기는 0이다. 다음 3번째 "bbab"는 주기로 "bba"를 예측할 수 있으므로 3이다. 4번째 "bbabb"는 "bbab"로 예측할 수 있다. 5번째 "bbabba"에서는 "bba"를 예측할 수 있다. 마지막 "bbabbab"에서는 "bbabba"를 예측할 수 있다. 여기서 i번째 문자의 예측가능 주기와 실패함수의 값 사이의 연관성을 찾아보자. 5번째 인덱스까지의 실패함수의 값은 3이다. 이 뜻은 0~2번째까지는 일치함이 보장된다는 것이고 그 문자열인 "bba"가 일치함이 보장된다는 의미아다. 똑같은 논리로 6번째 인덱스의 실패함수 값은 4이고, 이는 0~3번째 문자열인 "bbab"이다. 그렇지만 여기서 끝나는게 아니다. "bbabbab"로 예측할 수 있는 최대 문자열은 "bbabba"이기 때문이다. 3번째 인덱스에서 한번 더 거슬러 올라가야 한다. 따라서 fail[3]의 값인 인덱스 1로 거슬러 올라가야만이 최대로 예측할 수 있는 주기인 것이다. 즉, 핵심은 바로 0이 아닐 때까지 최대한 거슬러 올라가야 하는 것이다. 기존의 실패함수를 다시 쓰면,

0	1	2	3	4	5	6
b	b	a	b	b	a	b
0	1	0	1	1	3	1

으로 고쳐쓸 수 있다. 메모이제이션을 사용하면 O(N)만에 구할 수 있다.

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