백준 1305번 광고

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

KMP 알고리즘을 이용하여 접미사(prefix)도 되고 접두사(suffix)도 되는 문자열의 최대 길이를 저장하는 pi 벡터를 생성하면 쉽게 해결할 수 있는 문제였습니다.

물론 KMP 알고리즘을 직접 구현하는 것은 어려운 일이지만 다행스럽게도 "프로그래밍 대회에서 배우는 알고리즘 문제해결전략" 책에 상세한 설명과 함께 코드가 제공되기 때문에 그대로 작성했습니다.

전광판의 길이에서 접두사도 되면서 접미사도 되는 문자열의 최대 길이를 빼면 광고하고 싶은 내용을 알 수 있습니다!

#include <iostream>

#include <string>

#include <vector>

using namespace std;

 

int L;

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)

{

        cin >> L;

        cin >> S;

 

        vector<int> pi = getPartialMatch(S);

 

        cout << L - pi[L - 1] << endl;

        return 0;

}

개발환경:Visual Studio 2017

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

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