Cod sursa(job #710667)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 10 martie 2012 16:03:23
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir1[2000005], sir2[2000005];
int pi[2000005],pos[1024],n,m,i,q,nr;
inline void prefix()
{int i,q = 0;
    pi[i] = 0;
	for (i = 2;i<=m;++i)
	{	while (q && sir1[q+1] != sir1[i])
			q = pi[q];
		if (sir1[q+1] == sir1[i])
			++q;
		pi[i] = q;
	}
}
int main()
{   fin >> sir1 >> sir2;
    m = strlen(sir1);
	n = strlen(sir2);
	prefix();
	for (i=1;i<=n;++i)
	{	while (q && sir1[q+1] != sir2[i])
			q = pi[q];
		if (sir1[q+1] == sir2[i])
			++q;
		if (q == m)
		{	q = pi[m];
			++nr;
			if (nr <= 1000)
				pos[nr] = i-m;	
		}	
	}		
	fout << nr;
	for (i = 1; i <= min(nr,1000); ++i)
		fout << pos[i];
	return 0;
}