백준 4354번 문자열 제곱

문제 링크입니다: https://www.acmicpc.net/problem/4354

백준 1701번 Cubeditor(http://jaimemin.tistory.com/629) 문제 처럼 접미사 배열(Suffix Array)를 사용하여 푸는 문제였습니다.

문자열의 n 제곱이란 부분문자열을 n번 이어붙였을 때 해당 문자열이 나와야하기 때문에 접두사이면서 접미사인 부분문자열의 길이를 저장하는 벡터 pi를 구합니다.

문자열이 S일 때 인덱스가 S.length() - 1 일 때 접두사이면서 접미사인 부분문자열의 길이는 이미 문자열 a를 n번 제곱했을 떄의 부분문자열의 길이일 수 있습니다.

즉, S의 길이에서 인덱스가 S.length() - 1 일 때 부분문자열의 길이를 뺀 길이를 n번 제곱했을 때 S의 길이가 되게 해야하기 때문에 S.length() / (S.length() - pi[S.length()-1]) 를 출력해주면 AC를 받을 수 있는 문제였습니다.

"abcab"처럼 문자열 제곱수로 표현할 수 없지만 접두사와 접미사가 모두 될 수 있는 부분문자열("ab")가 있는 경우도 5/(5-2)가 계산되어 1이 출력되기 때문에 문제가 되지 않습니다!

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <functional>

using namespace std;

 

string S;

 

//N에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용해 pi[]를 계산

//pi[i] = N[..i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이

vector<int> getPartialMatch(const string &N)

{

        int M = N.size();

        vector<int> pi(M, 0);

        //KMP로 자기 자신을 찾는다

        //N을 N에서 찾는다

        //begin=0이면 자기 자신을 찾아버리니까 안됨!

        int begin = 1, matched = 0;

        //비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록

        while (begin + matched < M)

                 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(void)

{

        while (1)

        {

                 cin >> S;

                 if (S.length() == 1 && S[0] == '.')

                         break;

 

                 vector<int> pi = getPartialMatch(S);

 

                  

                 //팰린드롬도 고려

                 if (pi[S.length()-1] == 0 || pi[S.length() - 1] % (S.length() - pi[S.length() - 1]))

                         cout << 1 << endl;

                 else

                         cout << S.length() / (S.length() - pi[S.length()-1]) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략