[백준 4354] 문자열 제곱

문제

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

 

알고리즘

KMP

 

풀이

드디어 만나게 된 $S$에서 $W$를 찾는 단순한 KMP가 아닌, 실패 함수 자체만을 사용하는 문제입니다. 실패 함수에는 여러 성질 및 특징이 있지만, 자주 만나게 되는 세 가지 큰 특징이 있습니다. 그 중 하나를 소개하겠습니다.

 

문자열에서 A글자의 패턴을 만들 수 있음과 문자열의 앞쪽(N-A)글자와 뒤쪽 (N-A)글자가 같음은 동치

 

이 문제를 풀땐 위 특징을 적극 활용하여 풀어봅시다. 주어진 문자열 $S$에 대하여 실패함수를 구했다면, 우리는

$fail[slen-1]$ 이 가장 긴 접두사, 접미사의 길이임을 알게 됩니다. 문제에서 원하는 가장 큰  $n$을 구하기 위해선 반복되는 문자열의 길이가 가장 짧아야 하므로, 우리는 가장 긴 접두사, 접미사 즉 $fail[slen-1]$을 이용하게 됩니다. 즉 원하는

$n$은 $slen/(slen-fail[slen-1])$ 입니다. (1번 특징에서 설명하는 모든 a를 다 할 필요가  없음을 생각해봅시다. )

 

 

하지만 위와 같이 풀게 된다면 다음과 같은 반례에서 걸리게 됩니다

 

"ABCDABC" 

 

가장 긴 접두사, 접미사의 길이는 3이지만, 우리는 4에 해당하는 ABCD를 패턴으로 채택할 수 없습니다. 즉 

$slen/(slen-fail[slen-1])$을 정답으로 채택할 때는 나누어 떨어질 때만 임을 고려합시다.

 

코드

#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 main() {
    FAST;
    string S;
    int slen;
    while (1) {
        cin >> S;
        if (S == ".") break;
        slen = S.size();
        memset(fail, 0, sizeof(fail));

        for (int i = 1, j = 0;i < slen;++i) {
            while (j && S[i] != S[j]) j = fail[j - 1];
            if (S[i] == S[j]) fail[i] = ++j;
        }
        if (slen % (slen - fail[slen - 1])) cout << 1 << '\n';
        else cout << slen / (slen - fail[slen - 1]) << '\n';
    }

    return 0;
}