KMP의 Partial Match Table

백준 1305 광고 문제풀이

[1305 광고] https://www.acmicpc.net/problem/1305 .
KMP알고리즘 base의 failure function을 이용해서 문제의 답을 구한다.

문제상황 파악하기.

광고 문구가 될 수 있는 것중 가장 짧은 광고문구를 찾는 문제이다 .
광고가 될수 있는 문구 1글자, 2글자, 3글자… 씩 늘려가며 이 문구가 광고가 될 수 있나 검사할 수도 있지만 이는 O(N^2)의 시간복잡도가 걸릴 것이다.
따라서 O(N)으로 작동하는 KMP(knuth-moris-pratt)알고리즘을 이용할 것이다.

KMP와 failure function이 뭐길래?

이는 문자열(hey)을 검사할 때 검사하려는 문자(needle)의 pattern을 파악해 모든 부분을 검사하지 않고 넘기면서 검사하는 알고리즘이다.
그리고 그 pattern을 파악하는 부분도 KMP를 이용하고 이는 partial match table이라고 부른다.
그리고 pi 테이블을 만드는 함수를 failure function이라고 부른다.
이는 다른 블로그에서 간단하게 구현하는 것들이 있지만 나는 KMP알고리즘과 비슷하게 종만북을 참고하여 작성했다.
아래 코드는 pi table을 얻는 failure function이다.

vector<int> getPartialMatch(const string &N){
    int size = N.size();
    vector<int> pi(L, 0);
    
    int begin = 1, matched = 0;
    while (begin+matched<size) {
        if(N[begin+matched]==N[matched]){
            matched++;
            pi[begin+matched-1] = matched;
        }else{
            if(matched==0) begin++;
            else{
                begin += matched - pi[matched-1];
                matched = pi[matched-1];
            }
        }
    }
    
    return pi;
}

아이디어 얻기.

사실 pi를 만들었으면 게임 끝이다.
광고판에 나온 글자들은 어찌됐든 광고 문구안에 포함되어있는 문자들이다.

위 그림을 보면 PI의 마지막 값만 중요하다는 것을 알아낼 수 있다.
그러면 패턴하나의 크기만 알아내면 되므로
광고판 사이즈 - 마지막 PI의 값 = 정답!!!

주의할 점

딱히 주의할 점은 없다.
PI 테이블만 잘 만들면 문제 없기 때문이다.

실제 코드

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

int L;
vector<int> part;
//pi를 만든다
vector<int> getPartialMatch(const string &N){
    int size = N.size();
    vector<int> pi(L, 0);
    
    int begin = 1, matched = 0;
    while (begin+matched<size) {
        if(N[begin+matched]==N[matched]){
            matched++;
            pi[begin+matched-1] = matched;
        }else{
            if(matched==0) begin++;
            else{
                begin += matched - pi[matched-1];
                matched = pi[matched-1];
            }
        }
    }
    
    return pi;
}

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    cin >> L;
    string str;
    cin >> str;
    
    part = getPartialMatch(str);
    cout << part.size()-part.back();    //tablesize - pi마지막값
}