백준 1786번 : 찾기 - KMP 알고리즘

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

1786번: 찾기

#include <bits/stdc++.h>
using namespace std;

int* getLps(const string& _pattern_str){
    int pattern_len = _pattern_str.length();

    int *lps = (int *)malloc(sizeof(int)* pattern_len);
    memset(lps, 0, sizeof(int)*pattern_len);

    int j=0;
    for(int i=1;i < pattern_len; i++){
        while(j>0 && _pattern_str[i]!=_pattern_str[j]){
            j = lps[j-1];
        }

        if(_pattern_str[i] == _pattern_str[j]){
            j++;
            lps[i] = j;
        }
    }

    return lps;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    //Target, Pattern
    string T, P;
    getline(cin, T);
    getline(cin, P);

    int tLen = T.length();
    int pLen = P.length();
    int *lps = getLps(P);


    int cnt = 0;
    vector<int> v;

    int j = 0;

    for(int i=0; i<tLen; i++){
        while(j>0 && T[i]!=P[j]){
            j = lps[j-1];
        }

        if(T[i] == P[j]){
            if(j==pLen-1){
                v.push_back(i-pLen+1);
                cnt++;
                j = lps[j];
            }
            else{
                j++;
            }
        }

    }

    cout << cnt << '\n';
    for(auto i : v){
        cout << i + 1 << ' ';
    }


    delete lps;

    return 0;
}