백준 4354 : 문자열 제곱 (C++)

본문 링크

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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[i]==pattern[j])
        {
            table[i]=++j;
        }
    }


    return patternsize - table[table.size()-1];
}

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    string pattern;

    while (true)
    {
        cin >> pattern;

        if (pattern==".")
        {
            break;
        }

        int answer = maketable(pattern);

        if ( pattern.size()%answer==0)
        {
            cout << pattern.size()/answer << "\n";
        }
        else
        {
            cout <<  1 << "\n";
        }

    }
}

📌 어떻게 접근할 것인가?

KMP 응용문제입니다.

그냥 문제에서 원하는 것은 간단하게 말해서 문자열이 있을때

특정한 부분문자열을 반복해서 전체문자열을 만들 수 있는가? 를 묻습니다.

예를 들면 ababab 가 있을때 ab 를 3번 사용해서 전체 문자열을 만들 수 있습니다.

문제에서 원하는 것은 $N$ 의 최대값이므로

• 가장 짧은 부분문자열을 최대한 많이 사용해서 전체 문자열을 만들어라

와 같이 해석할 수 있습니다.

이때 사용해야 하는것은 실패함수입니다.

실패함수란 접두사와 접미사가 같은 문자의 개수를 저장하는 함수입니다.

개인적으로 이 문제를 풀기 전에 1305 : 광고 문제를 통해서 실패함수를 응용해보는것을 추천합니다.

실패함수의 마지막 값은 꽤 중요한 의미를 담습니다.

그것은 바로 전체 문자열에서 중복되는 부분문자열의 최대길이 를 의미합니다.

ababab 에서 실패 함수는 0 0 1 2 3 4 라는 값을 가지고
문자열의 길이 - 실패함수의 마지막 값은 중복되는 문자의 길이 입니다.

따라서 전체 문자열의 길이를 중복되는 문자의 길이로 나누면
중복되는 문자의 횟수를 구할수 있고 이는 3 이 됩니다.

왜냐하면 ababab 에서 ab 는 3번 반복해서 나타나기 때문이죠.

하지만 이때 주의할 점은 전체 문자열의 길이를 중복되는 문자로 나눈 나머지가 0 이 아닐때는
중복되는 문자를 여러번 사용해서 원래 문자열을 만들 수 없으므로 결국 문자 하나만을 사용해서 전체 문자열을 만들어야 하므로 $1$ 을 출력해야합니다.