백준 15881번 Pen Pineapple Apple Pen

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

겉보기에는 쉬운 문제 같지만 사실은 주어진 문자열에서 "pPAp" 형태를 띄는 부분 문자열을 찾는 KMP 알고리즘 문제였습니다.

함정이 있기 때문에 문제의 주의사항을 주목해야합니다!

단, 펜, 파인애플, 사과, 펜 순서로 연결된 네 개의 물건만을 펜-파인애플-애플-펜으로 인정하며, 하나의 펜이 두 개의 펜-파인애플-애플-펜에 포함될 수 없다. 또한 펜, 사과, 파인애플, 펜 순서로 연결된 네 개의 물건은 펜-파인애플-애플-펜이 아니다.

즉, 기존에 풀던 KMP 알고리즘 문제와 달리 부분 문자열("pPAp")를 찾으면 마지막 p를 재활용하지 못하기 때문에 matched=pi[matched-1]로 초기화하지 않고 matched=0으로 해서 새로 찾기 시작해야합니다.

#include <iostream>

#include <string>

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

        {

                 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;

}

 

//KMP 구현

int kmpSearch2(const string &H, const string &N)

{

        int n = H.size(), m = N.size();

        vector<int> result;

        vector<int> pi = getPartialMatch(N);

 

        //현재 대응된 글자의 수

        int matched = 0;

 

        //짚더미의 각 글자를 순회

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

        {

                 //matched번 글자와 짚더미의 해당 글자가 불일치할 경우

                 //현재 대응된 글자의 수를 pi[matched-1]로 줄인다

                 while (matched > 0 && H[i] != N[matched])

                         matched = pi[matched - 1];

                 //글자가 대응될 경우, 이미 pPAp에 쓰여진 p가 아니라면

                 if (H[i] == N[matched])

                 {

                         matched++;

                         if (matched == m)

                         {

                                 result.push_back(i - m + 1);

                                 //matched = pi[matched - 1];

                                 matched = 0; //pPAp의 마지막 p 재활용 불가능

                         }

                 }

        }

        return result.size(); //pPAp 등장 횟수 반환

}

 

int main(void)

{

        int N;

        cin >> N;

 

        string original, target;

        cin >> original;

       

        target = "pPAp"; //펜-파인애플-애플-펜

 

        cout << kmpSearch2(original, target) << endl;

        return 0;

}

개발환경:Visual Studio 2017

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

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