C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 1786번:찾기 답

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector <int> preprocessing(string p) {
    int psize = p.size();
    vector <int> pi(psize);
    pi[0] = 0;
    int j = 0;
    for (int i = 1; i < psize; i++)
    {
        while (j > 0 && p[i] != p[j])
        {
            j = pi[j - 1];
        }
        if (p[i] == p[j])
        {
            pi[i] = j + 1;
            j++;
        }
        else
            pi[i] = 0;
    }
    return pi;
}
vector <int> kmp(string s,string p)
{
    auto pi = preprocessing(p);
    vector <int> ans;
    int psize = p.size();
    int ssize = s.size();
    int j = 0;
    for (int i = 0; i < ssize; i++)
    {
        while (j > 0 && s[i] != p[j])//s는 전체 문자열, p는 찾으려는 문자열
        {
            j = pi[j - 1];
        }
        if (s[i] == p[j])
        {
            if (j == psize - 1)//마지막 문자열까지 같다면
            {
                ans.push_back(i - psize + 1);//위치를 저장
                j = pi[j];
            }
            else
                j += 1;
        }
    }
    return ans;
}
int main() {
    string s, p;
    getline(cin, s);
    getline(cin, p);
    auto matched = kmp(s, p);
    cout << matched.size() << '\n';
    for (auto index : matched)
        cout << index + 1 << ' ';
    cout << '\n';
}