Cod sursa(job #2456819)

Utilizator UnDragosDragos Ioana UnDragos Data 15 septembrie 2019 15:40:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb

#include <fstream>
#include <vector>

using namespace std;

int pi[2000005];
string A, B;

int main() {
	ios_base::sync_with_stdio(false);
	ifstream cin("strmatch.in");
	ofstream cout("strmatch.out");

	cin >> A >> B;

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

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

	pi[1] = 0;
	for (int i = 2, k = 0; i <= n; ++i) {
		while (A[i] != A[k + 1] && k != 0) k = pi[k];
		if (A[i] == A[k + 1]) ++k;
		pi[i] = k;
	}

	int nn = 0;
	vector<int> sol;
	for (int i = 0, j = 1; j <= m; ++j) {
		while (A[i + 1] != B[j] && i != 0) i = pi[i];
		if (A[i + 1] == B[j]) ++i;
		if (i == n) {
			if (sol.size() < 1000) sol.push_back(j - n);
			nn++;
			i = pi[i];
		}
	}

	cout << nn << "\n";
	for (auto i : sol) cout << i << " ";
	cout << "\n";

	return 0;
}