Cod sursa(job #377451)

Utilizator GotenAmza Catalin Goten Data 24 decembrie 2009 16:46:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream.h>

int i,prefix[2001000],poz[1100],k,nr,n,m;
char a[2001000],b[2001000];

int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f.getline(a,2001000);
	f.getline(b,2001000);
	n=strlen(a);
	m=strlen(b);
	for(i=n;i;i--)
		a[i]=a[i-1];
	for(i=m;i;i--)
		b[i]=b[i-1];
	prefix[1]=0;
	k=0;
	for(i=2;i<=n;i++)
	{
		while(k>0&&a[k+1]!=a[i])
			k=prefix[k];
		if(a[k+1]==a[i])
			k++;
		prefix[i]=k;
	}
	i=1;
	k=0;
	for(i=1;i<=m;i++)
	{
		while(k&&a[k+1]!=b[i])
			k=prefix[k];
		if(a[k+1]==b[i])
			k++;
		if(k==n)
		{
			k=prefix[n];
			nr++;
			if(n<=1000)
				poz[nr]=i-n;
		}
	}
	if(nr>1000)
		k=1000;
	else
		k=nr;
	g<<nr<<'\n';
	for(i=1;i<=k;i++)
		g<<poz[i]<<' ';
	return 0;
}