[백준 1787] 문자열의 주기 예측

문제

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

 

알고리즘

KMP, 동적 계획법

 

풀이

추정할 수 있는 문자열의 길이가 가장 길기 위해선 일치하는 prefix와 suffix가 가장 짧아야 함을 알 수 있습니다.

우리가 실패함수를 만들게 되면 일치하는 prefix와 suffix가 가장 긴 길이가 담겨 있게 됩니다. 문제에서 요구하는 것과는 정반대입니다. prefix와 suffix가 일치하는 길이가 1 이상인 가장 짧은 길이를 얻는 것은 동적 계획법을 통해 해결 가능합니다.

 

$cache[i]$ = 문자열의 길이가 $i+1$ 일 때, 동일한 prefix와 suffix의 길이중 0을 제외한 가장 짧은 값

 

현재 문자열의 길이를 $k$라 할 때, 일치하는 가장 긴 길이는 $fail[k-1]$ 이고, 그다음으로 긴 길이는 $fail[fail[k-1]-1]$ 입니다. 만약 두 번째로 긴 길이가 양수라면, $cache[k-1]$를 $cache[fail[k-1]-1]]$로 업데이트를 합시다. 반복적 동적 계획법을 사용하게 된다면 이 방식을 통해 모든 길이에 대한 가장 짧은 값을 구할 수 있습니다. 동적 계획법의 시간 복잡도와 실패 함수를 구하는 건 모두 $O(N)$에 가능합니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int fail[1000000];
int cache[1000000];
int N;
string S;
long long ans;
int main() {
    FAST;
    cin >> N >> S;
    for (int i = 1, j = 0;i < N;++i) {
        while (j && S[i] != S[j]) j = fail[j - 1];
        if (S[i] == S[j]) fail[i] = ++j;

        int k = i + 1;
        cache[i] = (fail[fail[k - 1] - 1] > 0 ? cache[fail[k - 1] - 1] : fail[k - 1]);
        if (!cache[i]) continue;
        if (i + 1 - cache[i] >= cache[i])
            ans += i + 1 - cache[i];
    }
    cout << ans;
    return 0;
}