Cod sursa(job #2271277)

Utilizator flibiaVisanu Cristian flibia Data 28 octombrie 2018 12:34:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

string a, b;
int sza, szb, phi[2000100], ans, sol[1010], vf;

void KMP() {
	int i = 1, j = 2;
	while (j <= sza) {
		while (i > 1 && a[j] != a[i])
			i = phi[i - 1] + 1;
		if (a[i] == a[j])
			phi[j] = i++;
		j++;
	}
}

void match() {
	int i = 1, j = 1;
	while (j <= szb) {
		while (i > 1 && b[j] != a[i])
			i = phi[i - 1] + 1;
		if (a[i] == b[j])
			i++;
		if (i > sza)
			sol[++vf] = j - sza;
		j++;
	}
	out << vf << '\n';
	for (int i = 1; i <= min(vf, 1000); i++)
		out << sol[i] << ' ';
}

int main() {
	in >> a >> b;
	sza = a.size();
	szb = b.size();
	a = '+' + a;
	b = '+' + b;
	KMP();
	match();
	return 0;
}