백준 13506번 : 카멜레온 부분 문자열 - KMP

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

13506번: 카멜레온 부분 문자열

#include <bits/stdc++.h>

#define MX 1'000'003
using namespace std;

bool check[MX];
char s[MX];

vector<int> getFail() {
    int len = strlen(s);
    vector<int> fail(len);
    for (int j = 0, i = 1; i < len; i++) {
        while (j > 0 && s[i] != s[j]) j = fail[j - 1];
        if (s[i] == s[j]) fail[i] = ++j;
        if (i != len - 1) check[j] = 1;
    }
    return fail;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    vector<int> fail = getFail();
    int len = strlen(s);

    for(int i=fail[len-1]; i>0; i= fail[i-1]){
        if(check[i]){
            s[i] = 0;
            cout << s << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
    
    return 0;
}