백준 소스코드 [C++] 1786 찾기

백준 소스코드 [C++] 1786 찾기

www.acmicpc.net/problem/1786

1786번: 찾기

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
typedef long long ll;
using namespace std;
vector<int> getPi(string sub) {
	vector<int> pi(sub.size(), 0);
	for (int i = 1, j = 0; i < sub.size(); i++) {
		while (j > 0 && sub[i] != sub[j]) j = pi[--j];
		if (sub[i] == sub[j]) pi[i] = ++j;
	}
	return pi;
}
vector<int> kmp(string target, string sub) {
	vector<int> res;
	vector<int> pi = getPi(sub);
	for (int i = 0, j = 0; i < target.size(); i++) {
		while (j > 0 && target[i] != sub[j]) j = pi[--j];
		if (target[i] == sub[j]) {
			if (j+1 == sub.size()) {
				res.push_back(i - j);
				j = pi[j];
			}
			else j++;
		}
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	string target, sub;
	getline(cin, target);
	getline(cin, sub);
	vector<int> res = kmp(target, sub);
	cout << res.size()<<'\n';
	for (int i = 0;i < res.size();i++) cout << res[i]+1 << " ";
	return 0;
}