백준13506 카멜레온 부분 문자열

작성일 | In

문제 링크

  • http://icpc.me/13506

사용 알고리즘

  • KMP

시간복잡도

  • $O(N)$

풀이

$S$의 Prefix이면서 동시에 Suffix인 것들의 길이는 $fail(N), fail(fail(N)), fail(fail(fail(N))), \cdots$ 뿐입니다.
Failure Function의 구축 과정을 잘 생각해보면, $fail(N)$을 제외한 $fail(fail(N)), fail(fail(fail(N))), \cdots$은 중간에 한 번 이상 더 나온다는 사실을 알 수 있습니다.

Failure Function을 구한 뒤, Failure Function을 쭉 따라가면서 정답을 구하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int N, Fail[1010101], A[1010101];
char S[1010101];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> S; N = strlen(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;
        if(i != N-1) A[Fail[i]] = 1;
    }
    for(int i=Fail[N-1]; i; i=Fail[i-1]) if(A[i]){ S[i] = 0; cout << S; return 0; }
    cout << -1;
}