Cod sursa(job #902109)

Utilizator raulstoinStoin Raul raulstoin Data 1 martie 2013 12:53:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#include<cstring>
#define NMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[NMAX],b[NMAX];
int p[NMAX],poz[1005],k,n,m,i,q;
void common(char x[],char y[])
{
	while(q && x[q+1]!=y[i])
		q=p[q];
	if(x[q+1]==y[i])
		q++;
}
void prefix()
{
	for(i=2,q=0;i<=m;i++)
	{
		common(a,a);
		p[i]=q;
	}
}
void kmp()
{
	for(i=1,q=0;i<=n;i++)
	{
		common(a,b);
		if(q==m)
		{
			q=p[m];
			k++;
			if(k<=1000)
				poz[k]=i-m;
		}
	}
}
void afisare()
{
	int i;
	g<<k<<'\n';
	if(k>1000)
		k=1000;
	for(i=1;i<=k;i++)
		g<<poz[i]<<' ';
	g<<'\n';
	g.close();
}
void citire()
{
	a[0]=b[0]=' ';
	f>>(a+1)>>(b+1);
	m=strlen(a)-1;
	n=strlen(b)-1;
	f.close();
}
int main()
{
	citire();
	prefix();
	kmp();
	afisare();
	return 0;
}