백준 1786번 찾기

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

백준 1305번 광고(http://jaimemin.tistory.com/625)와 마찬가지로 KMP 알고리즘을 사용하는 문제였습니다.

문제에서 KMP 알고리즘을 설명하고 KMP 알고리즘을 그대로 구현하라고 하기 때문에 "프로그래밍 대회에서 배우는 알고리즘 문제해결전략" 책을 갖고 있다면 수월하게 풀 수 있는 문제라고 생각됩니다.

주의할 점은 문제에서 문자열의 인덱스가 0이 아닌 1부터 시작한다고 간주한다는 점과 공백도 문자열에 포함되기 때문에 cin이 아닌 getline을 통해 T와 P를 입력받아야한다는 것입니다!

KMP 알고리즘의 보다 자세한 설명은 https://kks227.blog.me/220917078260를 참고하는 것을 추천드립니다!

#include <iostream>

#include <vector>

#include <string>

using namespace std;

 

string T, P;

 

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

}

 

vector<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];

                 //글자가 대응될 경우

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

                 {

                         matched++;

                         if (matched == m)

                         {

                                 //문제에서 인덱스는 0이 아닌 1부터 시작

                                 result.push_back(i - m + 2);

                                 matched = pi[matched - 1];

                         }

                 }

        }

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상 위해

 

        getline(cin, T); //공백 포함해서 입력받기 위해

        getline(cin, P);

 

        vector<int> result = kmpSearch2(T, P);

        //endl 쓰면 시간 초과

        cout << result.size() << "\n";

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

                 cout << result[i] << "\n";

        return 0;

}

개발환경:Visual Studio 2017

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

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