Cod sursa(job #529187)

Utilizator Oancea.CatalinOancea Catalin Oancea.Catalin Data 4 februarie 2011 14:51:29
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
using namespace std;
fstream f("strmatch.in", ios::in), g("strmatch.out", ios::out);
long long L[2000002], i, t, n, m, k, nrp, v[2002];
char P[2000002], T[2000002];
int main()
{
	f.getline(P,100);
	f.getline(T,100);
	
	n=strlen(P);
	for(i=n; i>=0; i--)
		P[i]=P[i-1];
	m=strlen(T);
	for(i=m; i>=0; i--)
		T[i]=T[i-1];
	k=0;
	L[1]=0;
	for(i=2; i<=n; i++)
	{
		while(k>0 && P[i]!=P[k+1])
			k=L[k];
		if(P[k+1]==P[i])
			k++;
		L[i]=k;
	}
	k=0;
	nrp=0;
	for(i=1; i<=m; i++)
	{
		while(k>0 && T[i]!=P[k+1])
			k=L[k];
		if(T[i]==P[k+1])
			k++;
		if(k==n)
		{
			nrp++;
			if(nrp<=1000)
				v[nrp]=i-n;
			k=L[k];
		}
	}
	g<<nrp<<endl;
	if(nrp<=1000)
	{
		for(i=1; i<=nrp; i++)
			g<<v[i]<<" ";
	}
	else
	{
		for(i=1; i<=1000; i++)
			g<<v[i]<<" ";
	}
}