백준 1308번

문제 해설이 아닌 풀이하면서 거쳐간 생각들을 기록하는 글입니다.

문제

세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다.

전광판에는 같은 내용의 문구가 무한히 반복되어 나온다. 또, 전광판의 크기는 전광판에서 한번에 보이는 최대 문자수를 나타낸다. 만약 전광판의 크기가 L이라면, 한번에 L개의 문자를 표시할 수 있는 것이다.

광고업자는 최대한의 광고효과를 내기 위해서 길이가 N인 광고를 무한히 붙여서 광고한다.

예를 들어, 광고 업자 백은진이 광고하고 싶은 내용이 aaba 이고, 전광판의 크기가 6이라면 맨 처음에 보이는 내용은 aabaaa 이다. 시간이 1초가 지날 때마다, 문자는 한 칸씩 옆으로 이동한다. 따라서 처음에 aabaaa가 보였으면 그 다음에는 abaaab가 보인다. 그 다음에는 baaaba가 보인다.

세준이가 어느 순간 전광판을 쳐다봤을 때, 그 때 쓰여 있는 문자가 입력으로 주어졌을 때, 가능한 광고의 길이중 가장 짧은 것을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다.

출력

첫째 줄에 가능한 광고의 길이중 가장 짧은 것의 길이를 출력한다.

제한

1 ≤ L ≤ 1,000,000
광고판에 보이는 문자열은 알파벳 소문자로만 이루어져 있다.

접근 과정

어제에 이어 KMP 문제를 골라보았다. 전광판 시작 부분의 문자열이 전광판 오른쪽 끝에 위치한 부분 문자열과 겹친다면 오른쪽 끝부분이 새로 등장하는 광고문구의 시작 부분이라 볼 수 있다. 오른쪽 끝 문자열이 시작 부분으로부터 얼마나 일치하였는지 확인할 수 있다면 최소가 되는 광고문구의 길이를 구할 수 있다.
KMP 알고리즘의 실패함수는 단인 문자열의 위치별로 시작 문자열로부터 몇 문자가 일치하는지 구할 수 있다. 따라서 실패함수를 구현하여 오른쪽 끝 문자가 전광판 시작 문자로부터 몇 문자가 일치하였는지 계산하고 이를 전광판의 총 길이에서 빼주면 문제가 요구하는 최소 길이를 구할 수 있다.
KMP 알고리즘 관련 문제라는 걸 알았기에 금방 풀 수 있었지만 몰랐다면 방법을 바로 생각할 수 있었을지 모르겠다. 알고리즘에 익숙해지는 수밖에 없는 걸까?

소스 코드

#include <iostream>
#include <string>
#include <vector>

std::vector<int> pTable;

void calcPatternTable(const std::string& pattern) {
    pTable.reserve(pattern.size());
    pTable.push_back(0);
    
    unsigned int k = 0;
    for (unsigned int i = 1; i < pattern.size(); ++i) {
        while (k > 0 && pattern[i] != pattern[k]) {
            k = pTable[k - 1];
        }

        if (pattern[i] == pattern[k]) {
            ++k;
        }
        pTable.push_back(k);
    }
}

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);

    int n;
    std::string s;
    std::cin >> n;

    s.reserve(n);
    std::cin >> s;

    calcPatternTable(s);
    std::cout << n - pTable.back();
    return 0;
}