Cod sursa(job #685634)

Utilizator Robert29FMI Tilica Robert Robert29 Data 21 februarie 2012 08:22:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
#include<fstream>
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
int nr,n,m,v[1001],p[2000004];
char a[2000004],b[2000004];

void prep()
{
	int k=0;
	p[1]=0;
	for(int i=2;i<=n;++i)
	{
		while(k&&a[i]!=a[k+1])
			k=p[k];
		if(a[i]==a[k+1])
			++k;
		p[i]=k;
	}
}
void kmp()
{
	int q=0;
	
	for(int i=1;i<=m;++i)
	{
		while(q&&b[i]!=a[q+1])
			q=p[q];
		if(b[i]==a[q+1])
			++q;
		if(q==n)
		{
			++nr;
			if(nr<=1000)
				v[nr]=i-n;
		}
	}
	
	
}
int main()
{
	fscanf(f,"%s",a+1);
	fscanf(f,"\n");
	fscanf(f,"%s",b+1);
	
	for(n=1;a[n];++n);
	--n;
	for(m=1;b[m];++m);
	--m;
	
	prep();
	kmp();
	
	fprintf(g,"%d\n",nr);
	if(nr>1000)
		nr=1000;
	for(int i=1;i<=nr;++i)
		fprintf(g,"%d ",v[i]);
	
	
	fclose(g);
	fclose(f);
	return 0;
}