Cod sursa(job #710676)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 10 martie 2012 16:13:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<fstream>
#include<cstring>
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[1] = 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);
	for (i=m+1;i>=1;--i)
		sir1[i] = sir1[i-1];
	for (i=n+1;i>=1;--i)
		sir2[i] = sir2[i-1];
	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 << '\n';
	for (i=1;i<= min(nr,1000);++i)
		fout << pos[i] << " ";
	return 0;
}