Algospot PALINDROMIZE

문제 링크입니다: https://algospot.com/judge/problem/read/PALINDROMIZE

KMP 알고리즘을 통해 팰린드롬을 구성하는 가장 짧은 문자열의 길이를 구하는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 주어진 문자열을 입력 받은 다음 뒤집은 문자열을 만듭니다.

2. 두 문자열을 합쳤을 때 접두사와 접미사가 최대로 겹치는 길이를 KMP 알고리즘을 통해 구합니다.

3. "주어진 문자열의 길이(문자열 + 뒤집은 문자열) * 2 - 2번에서 구한 길이" 가 정답입니다.

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

using namespace std;

 

//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)

        {

                 //begin+matched에 있는 문자와 matched에 있는 문자 일치

                 if (N[begin + matched] == N[matched])

                 {

                         ++matched;

                         pi[begin + matched - 1] = matched;

                 }

                 //일치하지 않고

                 else

                 {

                         //matched가 0인 경우 begin을 한칸 앞으로

                         if (matched == 0)

                                 ++begin;

                         //matched가 0이 아니면

                         else

                         {

                                 //begin을 (matched - 일치하는 접미사/접두사의 길이)만큼 더한다

                                 begin += matched - pi[matched - 1];

                                 matched = pi[matched - 1];

                         }

                 }

        }

        return pi;

}

 

//a의 접미사이면서 b의 접두사인 문자열의 최대 길이를 구한다

int maxOverlap(const string &a, const string &b)

{

        int n = a.size(), m = b.size();

        //reversed에 대해서 getPartialMatch

        vector<int> pi = getPartialMatch(b);

        //begin=matched=0에서부터 시작

        int begin = 0, matched = 0;

 

        while (begin < n)

        {

                 //만약 짚더미의 해당 글자가 바늘의 해당 글자와 같다면

                 if (matched < m && a[begin + matched] == b[matched])

                 {

                         ++matched;

                         if (begin + matched == n)

                                 return matched;

                 }

                 //글자가 같지 않으면 getPartialMatch와 동일하게

                 else

                 {

                         if (matched == 0)

                                 ++begin;

                         else

                         {

                                 begin += matched - pi[matched - 1];

                                 matched = pi[matched - 1];

                         }

                 }

        }

        return 0;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 string original, reversed;

                 cin >> original;

 

                 for (int i = original.size() - 1; i >= 0; i--)

                         reversed += original[i];

 

                 //원래 문자열과 뒤집은 문자열을 합친 뒤 Suffix와 Prefix끼리 겹치는 만큼 빼면 가장 짧은 문자열

                 int result = original.length() * 2 - maxOverlap(original, reversed);

 

                 cout << result << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

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

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