백준 1305 : 광고 (C++)

본문 링크

#include <iostream>
#include <vector>

using namespace std;

vector<int> maketable(string pattern)
{
    int patternsize = pattern.size();
    vector<int> table (patternsize,0);

    int j=0;

    for (int i = 1; i < patternsize ; i++)
    {
        while (j>0 && pattern[i]!=pattern[j])
        {
            j=table[j-1];
        }

        if (pattern[j]==pattern[i])
        {
            table[i]=++j;
        }
    }

    return table;
}

int main()
{

    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int N;

    cin >> N;

    cin.ignore();

    string pattern;

    getline(cin , pattern);

    vector<int> table = maketable(pattern);

    cout << N-table[table.size()-1];

}

📌 어떻게 접근할 것인가?

KMP 응용 문제입니다.

문제를 좀 이해하는데 오래 걸렸습니다.

현재 광고판에 보이는 문자열이 cabcab 라고 가정해봅시다.

광고판은 매번 가장 오른쪽 문자가 왼쪽 문자로 이동합니다. 구하고자 하는 것은

• 최소 몇개의 문자열로 저 광고판을 만들수 있는가?

입니다. 이때 답은 abc , 즉 3가 됩니다.

인덱스를 0 부터 시작한다고 한다면 1부터 3까지 abc 를 만들 수 있고
4~5 와 0번째 인덱스를 포함해서 abc 를 만들 수 있습니다.

문제의 핵심은

• 문자열의 마지막이 접두사와 중복된 채로 끝난다면 해당 중복 문자열의 길이만큼 광고 문자열을 감소시킬 수 있다.

위와 같습니다.

즉 문자열의 전체길이에 실패함수의 마지막 값을 빼면 중복되지 않은 문자열의 길이를 구할 수 있습니다.

왜냐하면 실패함수의 마지막 값이란 , 접미사와 접두사의 공통 부분이므로 공통부분을 제외하고 나머지 부분이 광고판에 필요한 최소 문자열의 길이이기 때문입니다.

따라서 문자열의 전체 길이에서 실패함수의 마지막 값을 빼면 필요한 문자열의 최소길이를 구할 수 있습니다.