KMP Best Practice

cpp nlogn

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
 
using namespace std;
 
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string t, s; getline(cin, t); getline(cin, s);
	int ts = t.size(); int ss = s.size();
	vector<int> pi(ss);//pi[x] = y 일 때, x 지점에서 이전 문자열과 y만큼 접 미/두 사가 일치함.
	// 부분 문자열 별 접두사 접미사 최대 중첩 길이 전처리
	int cur = 0;//부분 문자열 포인터
	for (int i = 1; i < ss; i++) {		
		while (cur > 0 && s[i] != s[cur]) {
			cur = pi[cur - 1];//이전 접 미/두 사 일치 자리 찾기
		}
		if (s[i] == s[cur]) {//현재 자리가 일치한다면 
			pi[i] = ++cur;// 저장하고 다음 자리 확인
		}
	}
	cur = 0;//부분 문자열 위치 포인터
	vector<int> pos;
	for (int i = 0; i < ts; i++) {
		while (cur > 0 && t[i] != s[cur]) { // 문자열의 시작 지점이 일치하는 지점 탐색
			cur = pi[cur - 1];
		}
		if (t[i] == s[cur]) { // 일치할 경우 
			if (cur == ss - 1) { // 정해진 길이를 채웠을 경우
				pos.push_back(i - ss + 2); // 시작 지점 검색
				cur = pi[cur]; // 전체 문자열이 일치했으므로 다음 탐색은 현재 부분 문자열 접 미/두 사가 일치하는 지점부터 탐색 시작
			}
			else {
				cur++; //다음 탐색 지점 검색
			}
		}
	}
	cout << pos.size() << "\n";
	for (const auto& p : pos) {
		cout << p << "\n";
	}
	return 0;
}