BOJ)13506 카멜레온 부분 문자열

문제: icpc.me/13506

접두사와 접미사가 동시에 될 수 있는 최대 부분 문자열 중 접두사와 접미사가 둘다 아니게도 등장하는 부분 문자열을 카멜레온 부분 문자열이라고 할 때 카멜레온 부분 문자열중에서 가장 길이가 긴 부분 문자열을 출력하는 문제이다.

KMP의 pi배열을 이용한다면 우리는 prefix와 suffix를 동시에 만족시키는 모든 문자열의 길이를 알 수 있다 // pi[l] -> pi[pi[l]] ->pi[pi[pi[l]]] ...

이 때 prefix와 suffix를 둘 다 만족안하게 등장하는 경우는 pi[0]과 pi[length]를 제외하고 현재 확인하는 부분문자열의 길이와 같은 pi[x]가 존재하는 경우이다.

 

#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int> pi;
string a;
void getpi() {
    pi.resize(a.length());
    int j = 0;
    for (int i = 1; i < a.length(); i++) {
        while (j&&a[i] != a[j])
            j = pi[j - 1];
        if (a[i] == a[j])
            pi[i] = ++j;
    }
}
int main() {
    cin >> a;
    getpi();
    int x = pi[a.length() - 1];
    int f = 0;
    while (x) {
        for (int i = 1; i < a.length() - 1; i++)
            if (pi[i] == x) {
                for (int j = 0; j < x; j++)
                    printf("%c", a[j]);
                f = 1;
                break;
            }
        if (f)break;
        x = pi[x - 1];
    }
    if (!f)puts("-1");
    return 0;
}