Cod sursa(job #170016)

Utilizator hadesgamesTache Alexandru hadesgames Data 2 aprilie 2008 12:22:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <string.h>
char a[2000010],b[2000010];
int sol[60010],pi[2000010];
int main()
{
	FILE *in,*out;
	int i,k,nr=0,n,m;
	in=fopen("strmatch.in","r");
	out=fopen("strmatch.out","w");
	fscanf(in,"%s",a+1);
	fscanf(in,"%s",b+1);
	n=strlen(a+1);
	m=strlen(b+1);
	pi[1]=0;
	k=0;
	for (i=2;i<=n;i++)
	{
		while (k>0&&a[k+1]!=a[i])
			k=pi[k];
		if (a[k+1]==a[i])
			k++;
		pi[i]=k;
                     
	}
	k=0;
	for (i=1;i<=m;i++)
	{
		while (k>0&&a[k+1]!=b[i])
			k=pi[k];
		if (a[k+1]==b[i])
			k++;
		if (k==n&&nr<1005)
		{
			nr++;
			sol[nr]=i-n;
		}
	}

	fprintf(out,"%d\n",nr);

	for (i=1;i<=nr&&i<=1000;i++)
	{
		fprintf(out,"%d ",sol[i]);
	}		
	fclose(in);
	fclose(out);
	return 0;
}