백준 1701번 Cubeditor

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

접두사도 되면서 접미사도 되는 부분 문자열 중 최대 길이를 구하는 문제였습니다.

즉, 백준 1786번 찾기(http://jaimemin.tistory.com/627)에서의 getPartialMatch 함수를 사용하면 되는 문제였습니다.

하지만, 함정이 있다면 getPartialMatch 함수는 문자열이 S라고 할 때 S[0]을 시작으로 하는 접두사에 대해서만 조사를 하기 때문에 "abbcbba"와 같은 시스템 케이스가 주어진다면 AC를 받을 수 없습니다.

왜냐하면, "abbcbba"에서 원하는 답은 "bb"의 길이 즉, 2인데 getPartialMatch 함수에서는 접두사와 접미사가 모두 되는 문자열은 "a" 뿐이기 때문에 1을 반환합니다.

따라서 문자열의 시작 인덱스를 바꿔가면서 getPartialMatch 함수를 호출하고 그 중 최대 길이를 출력하면 AC를 받을 수 있습니다.

string은 pop_front를 지원하지 않기 때문에 substr 함수를 통해 문자열의 시작 인덱스를 바꿔나가면 됩니다!

#include <iostream>

#include <algorithm>

#include <functional>

#include <string>

#include <vector>

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)

{

        cin >> S;

 

        //접미사도 되고 접두사도 되면 이미 2번 출현한 것이므로 여기서 최대길이 출력

        int result = 0;

        for (int i = 0; i < S.size(); i++)

        {

                 string temp=S.substr(i, S.size()); //문자열의 pop_front 같은 역할

                 vector<int> pi = getPartialMatch(temp);

                

                 sort(pi.begin(), pi.end(), greater<int>());

                 result = max(result, pi[0]);

        }

 

        cout << result << endl;

        return 0;

}

개발환경:Visual Studio 2017

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

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