Cod sursa(job #2838087)

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

using namespace std;

const int MAXN = 2e6;

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

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

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

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

		pi[i] = k;
	}
}

int KMP(string A, string B, int *pi, vector<int> &ans) {
	int cnt = 0;

	int n = A.size();
	int m = B.size();

	A = " " + A;
	B = " " + B;

	int k = 0;

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

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

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

	return cnt;
}

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);

	

	cout << KMP(A, B, pi, ans) << '\n';
	for (auto x : ans)
		cout << x << ' ';
	cout << '\n';

	return 0;
}