Cod sursa(job #2838083)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 23 ianuarie 2022 02:02:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e6;

int pi[MAXN + 2];
string A, B;

void calcPi(string S, int *pi) {
	int n = S.size();
	pi[0] = 0;
	int k = 0;

	for (int i = 1; i < n; ++ i) {
		while (k > 0 && S[k] != S[i])
			k = pi[k - 1];

		if (S[k] == S[i])
			++ k;

		pi[i] = k;
	}
}

void KMP(string A, string B, int *pi, vector<int> &ans) {
	int n = A.size();
	int m = B.size();

	int k = 0;

	for (int i = 0; i < m; ++ i) {
		while (k > 0 && A[k] != B[i])
			k = pi[k - 1];

		if (A[k] == B[i])
			++ k;

		if (k == n && ans.size() < 1000)
			ans.push_back(i - n + 1);
	}
}

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);


	cin >> A >> B;

	vector<int> ans;
	calcPi(A, pi);

	KMP(A, B, pi, ans);

	cout << ans.size() << '\n';
	for (auto x : ans)
		cout << x << ' ';
	cout << '\n';

	return 0;
}