Cod sursa(job #662139)

Utilizator lily3Moldovan Liliana lily3 Data 15 ianuarie 2012 21:56:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#include<cstring>
using namespace std;

int i,j,n,m,rez=0,urm[2000002],sol[1005];
char a[2000002],b[2000002];
void prefix()
{
	int i,k=0;
	for(i=2;i<=n;++i)
	{
		while(k&&a[k+1]!=a[i])
			k=urm[k];
		if(a[k+1]==a[i])
			++k;
		urm[i]=k;
	}
}
void rezolva()
{
	int i,k=0;
	for(i=1;i<=m;++i)
	{
		while(k&&a[k+1]!=b[i])
			k=urm[k];
		if(a[k+1]==b[i])
			++k;
		if(k==n)
		{
		k=urm[n];
		if(rez<1000)
		sol[rez]=i-n;
		rez++;
		}
	}
}
int main()
{
	FILE *f=fopen("strmatch.in","r");
	FILE *g=fopen("strmatch.out","w");
	fscanf(f,"%s%s",a+1,b+1);
	n=strlen(a+1);
	m=strlen(b+1);
	urm[1]=0;
	if(n>m)
		fprintf(g,"0\n");
	else
	{
	prefix();
	rezolva();
	fprintf(g,"%d\n",rez);
	for(i=0;i<rez&&i<1000;++i)
		fprintf(g,"%d ",sol[i]);
	}
	return 0;
}