Cod sursa(job #170010)

Utilizator hadesgamesTache Alexandru hadesgames Data 2 aprilie 2008 12:19:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>
#include <string.h>
char a[2000010],b[2000010];
int sol[10010],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++;
			sol[nr]=i-n;
			if (nr==1000&&n>1000)
			{
				fprintf(out,"%d\n",nr);
				for (i=1;i<=nr;i++)
				{
					fprintf(in,"%d ",sol[i]);
				}
				fclose(in);
				fclose(out);
				return 0;
			}
		}
	}

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

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