[C++] 1786번 찾기 - 문자열, KMP

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int cnt;
string text, pattern;

vector<int> Fail()
{
    int m = pattern.length();
    vector<int> pi(m);
    
    pi[0]=0;
    for(int i=1, j=0; i<m; i++) {
        while(j>0 && pattern[i]!=pattern[j]) j=pi[j-1];
        if(pattern[i] == pattern[j]) pi[i] = ++j;
    }
    return pi;
}

vector<int> KMP()
{
    int m = pattern.length();
    int n = text.length();
    
    vector<int> pos;
    vector<int> pi = Fail();
    
    for(int i=0, j=0; i<n; i++) {
        while(j>0 && text[i]!=pattern[j]) j=pi[j-1];
        if(text[i] == pattern[j]) {
            if(j==m-1) {
                pos.push_back(i-m+2);
                j = pi[j];
                cnt++;
            }
            else j++;
        }
    }
    
    return pos;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    getline(cin, text); getline(cin, pattern);
    
    vector<int> pos = KMP();
    
    cout << cnt << '\n';
    for(int i=0; i<pos.size(); i++) cout << pos[i] << ' ';
    
    return 0;
}

KMP 알고리즘은 처음 보는 알고리즘이라서 다른 사람이 설명해놓은 글을 참고했다. 참고한 사이트는 아래에 적어놨다.

 

 

 

<KMP 알고리즘>

https://ansohxxn.github.io/algorithm/kmp/

(C++) 문자열 검색 알고리즘 : KMP 알고리즘

 

<공백 포함 문장려 입력받기>

https://aeunhi99.tistory.com/114

[C++] 공백(띄어쓰기)포함 문자열 입력받기

 

 

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.