[c++] 백준 1786 - 찾기(KMP, getline)

0. [c++] 백준  -

https://www.acmicpc.net/problem/1786

1. 풀이

이번 문제는 KMP알고리즘이라는 검색 알고리즘을 활용해보았다.

KMP알고리즘은 검색을 하면서 불필요한 반복을 줄이기 위해, 검색의 key가 되는 문자열의 접두사와 접미사의 중복 길이를 배열로서 따로 구현을 한다.

이제 검색은 한 단어씩 비교를 하게 되는데, 비교를 하면서 틀린 부분이 발생하는 경우, 미리 구해놓은 일정 구간을 건너 뛰어서 검색을 하게 된다. 이게 KMP알고리즘의 핵심 개념이고, 이제 이를 활용해서 문제를 풀어보았다.

이제 첫번째 구현이라 그저 책을 보고 따라했는데, 익숙해질때까지 문제를 많이 풀어보아야겠다.

+)문제를 풀면서 제한시간 초과를 하는 문제가 발생했었는데, endl의 사용이 문제가 되어서 시간이 초과했었다.

endl은 개행문자를 넣어주면서 버퍼를 초기화 한다고 알고 있었는데, 많은 양의 데이터가 저장되어있는 버퍼를 초기화 하는 과정에서 오류가 발생한 걸까?

시간 초과를 하게 된 이유는 나중에 추가적으로 찾아보자.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

#include<iostream> #include<string> #include<vector>   using namespace std;   string T, P;   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> ret;     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) {                 ret.push_back(i - m + 1);                 matched = pi[matched - 1];             }         }     }     return ret; }       int main() {     /*ios_base::sync_with_stdio(0);     cin.tie(0);*/       getline(cin, T);     getline(cin, P);       /*cout << T << endl;     cout << P << endl;*/          vector<int> ret;     ret = kmpSearch2(T, P);       cout << ret.size() << "\n";     for (int i = 0; i < ret.size(); i++) {         cout << ret[i] + 1 << "\n";     }       return 0; }     Colored by Color Scripter

cs

3. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.643~657

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!