[BOJ] 1786 : 찾기

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;

const int N_ = 1e6 + 5;

int fail[N_], t_len, p_len;
char T[N_], P[N_];

int main() {
	gets_s(T); t_len = strlen(T);
	gets_s(P); p_len = strlen(P);

	for (int i = 1, j = 0; i < p_len; ++i) {
		while (j && P[i] != P[j]) j = fail[j - 1];
		if (P[i] == P[j]) fail[i] = ++j;
	}

	vector<int> ans;
	for (int i = 0, j = 0; i < t_len; ++i) {
		while (j && T[i] != P[j]) j = fail[j - 1];

		if (T[i] == P[j]) {
			if (j == p_len - 1) {
				ans.push_back(i - p_len + 2);
				j = fail[j];
			}
			else ++j;
		}
	}

	printf("%d\n", ans.size());
	for (auto p : ans) printf("%d ", p);

	return 0;
}