Cod sursa(job #662133)

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

int i,j,n,m,rez=0,urm[2000001],sol[1001];
char a[2000001],b[2000001];
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=2;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;
		}
	}
}
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;
	prefix();
	rezolva();
	fprintf(g,"%d\n",rez);
	for(i=1;i<=rez;++i)
		fprintf(g,"%d ",sol[i]);
	return 0;
}