[Baekjoon,4354] 문자열 제곱

주어진 문자열 s가 부분 문자열 a로 최대로 몇 번 반복해서 이을 수 있는지 찾아야 한다. 예를 들어 문자열 $s=abaabaaba$가 있으면 이는 문자열 $a=aba$를 $3$번 이어 만들 수 있다.

접두사와 접미사

이를 찾는 방법은 문자열의 접두사 접미사가 어떻게 일치하는지를 보면 알 수 있다. 위에서 예로 든 문자열 $s$를 보자. $s$는 문자열 $abaaba$가 접두사이며 접미사인 것을 볼 수 있다. 이는 $s$의 길이 $9$에서 접두사와 동시에 접미사인 문자열의 길이 $6$을 뺀 $3$을 $s$의 길이에 나누면 $9\div 3=3$인 것을 알 수 있다.
이번에는 다른 문자열을 보자 $whatwhat$을 보면 이는 $what$이 $2$번 이어져 만들어 진 것을 볼 수 있다. 이 또한 $8\div 4=2$인 것을 알 수 있다.

그렇다면 어떻게 접두사이며 접미사인 문자열을 구할까? 이는 $KMP$알고리즘이 $failure$ 함수를 구하는 과정을 이용하면 된다. 즉, 문자열의 어느 인덱스에서 접두사도 되고 접미사도 되는 부분 일치 테이블을 찾는 과정으로 구한 배열의 마지막 인덱스 값을 확인하면 된다. 그런데 이 값이 문자열 길이의 절반보다 작다면 특정 문자열 $a$를 이어 문자열 $s$를 만들 수 없다.

구현

이를 구현한 코드를 아래에서 볼 수 있다.

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

vector<int> getPartialMatch(const string& s)
{
    int n=s.size();
    vector<int> pi(n,0);
    int matced=0;
    for(int i=1;i<n;++i)
    {
        while(matced>0 && s[i]!=s[matced])
            matced=pi[matced-1];
        if(s[i]==s[matced])
        {
            ++matced;
            pi[i]=matced;
        }
    }
    return pi;
}

int solve(const string& s)
{
    vector<int> pi=getPartialMatch(s);
    int len=s.size();
    
    int k=len-pi[len-1];
    if(len%k!=0)
        return 1;
    return len/k;
}

int main()
{
    while(true)
    {
        string s;
        cin>>s;
        if(s==".")
            break;
        cout<<solve(s)<<endl;
    }

    return 0;
}