[C++ 백준 풀이] 13506번 : 카멜레온 부분 문자열 (KMP)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 13506번 : '카멜레온 부분 문자열' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Platinum 티어에 해당하며, 문제를 풀이하기 위해 KMP 알고리즘에 대한 이해가 필요합니다.

 

 

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

 

입력받은 문자열의 접두사이면서 접미사이면서 문자열 중간에도 등장(이 때 세 위치가 모두 달라야 함)하는 가장 긴 문자열을 출력하는 문제입니다.

당연히 단순 브루트포스 탐색으로는 시간 제한을 통과하지 못하므로, KMP 알고리즘의 Pi 배열을 응용하여 해결하는 문제입니다.

 

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> GetPi(string Pattern) {
    vector<int> Pi(Pattern.length());
    for(int i=1, j=0; i<Pattern.length(); i++) {
        while(j>0 && Pattern[i] != Pattern[j]) j = Pi[j-1];
        if(Pattern[i] == Pattern[j]) Pi[i] = ++j;
    }
    return Pi;
}

int main() {
    string Str;
    cin >> Str;
    vector<int> Pi = GetPi(Str);
    int L = Str.length(), Max = Pi[L-1];
    while(Max > 0) {
        for(int i=1; i<L-1; i++)
            if(Pi[i] == Max) {
                cout << Str.substr(0, Max);
                return 0;
            }
        Max = Pi[Max-1];
    }
    cout << "-1";
}

 

Pi 배열을 응용하여 생각해보면 접두사 = 접미사인 위치는 Pi[L], Pi[Pi[L]], Pi[Pi[Pi[L]]], ...이므로 이를 활용하여 가운데에 등장하는 접두사 = 접미사 = 부분 문자열인 부분 문자열을 찾을 수 있습니다.

 

 

 

너무 간단히 설명하기에는 부족한 감이 있으니, 알고리즘이 작동하는 원리를 예제 입력 3인 "papapapap"를 이용하여 설명해두었습니다.

위의 그림을 참고하여 알고리즘의 작동 원리를 파악하시면 쉬울 것입니다.