1786 찾기 백준

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>
 
using namespace std;
 
string T;
string P;
vector<int> pi;
 
int main() {
    getline(cin, T);
    getline(cin, P);
    
    // pi 배열 완성하기
    int lenP = P.size();
    int cmp = 0; //비교를 하는 앞부분 idx
    vector<int> pi(lenP+1, 0);
 
    for (int i = 1; i < lenP; i++) {
        while (cmp > 0 && P[i] != P[cmp])    
            cmp = pi[cmp - 1];        // 일치하지 않을 경우, parent로 이동
        if (P[cmp] == P[i])
            pi[i] = ++cmp;        
    }
 
    // pi배열을 이용해서 KMP연산 하기
    int lenT = T.size();
    int cmpidx = 0;    
    vector<int> tmp;
    for (int i = 0; i < lenT; i++) {
        while (cmpidx > 0 && P[cmpidx] != T[i]) {
            cmpidx = pi[cmpidx - 1];
        }    // pi 구하는 과정과 유사
        if (T[i] == P[cmpidx]) {
            if (cmpidx == lenP - 1) {
                tmp.push_back(i - cmpidx);
                cmpidx = pi[cmpidx];    // 완성했을때, 원래의 모양으로 초기화 시켜줘야함
            }
            else
                cmpidx++;
        }        
    }    
    //결과 출력
    printf("%d\n", tmp.size());
    for (int i = 0; i < tmp.size(); i++)
        printf("%d ", tmp[i]+1);
}