Cod sursa(job #1435677)

Utilizator BabutaRaresBabuta Rares Mihai BabutaRares Data 14 mai 2015 00:57:47
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#include<string>
using namespace std;

int* prefix(string p, int m)
{
	int *f = new int[m + 1];
	f[0] = -1;
	int k;
	for (int j = 1; j < m; j++)
	{
		k = f[j - 1];
		while (k != -1 && p[j - 1] != p[k])
			k = f[k];
		f[j] = k + 1;
	}
	return f;
}
int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	string p, s;
	f >> p >> s;
	const int m = p.size(), n = s.size();
	int *F = new int[m + 1];
	F = prefix(p, m);
	int i, j;
	i = j = 0;
	int sol = 0, v_sol[1001];
	while (i < n)
	{
		while (j != -1 && s[i] != p[j])
			j = F[j];
		if (j == m - 1 && sol<1000){ sol++; v_sol[sol] = i - m + 1; j = 0; }
		else
		{
			i++; j++;
		}
	}
	g << sol << "\n";
	for (i = 1; i <= sol; i++)
		g << v_sol[i] << " ";
}