Cod sursa(job #584445)

Utilizator bugyBogdan Vlad bugy Data 25 aprilie 2011 16:08:51
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<stdio.h>
#include<string.h>
#define dim 2000001
#define minim(a,b) (a < b ? a : b)
using namespace std;

int n,m,nr,v[1001],urm[dim],i,x,k;
char P[dim],T[dim];

void urmatorul()
{
	urm[0]=k=-1;
	
	for(x=1;x<m;x++)
	{
		while(k>-1 && P[k+1]!=P[x])
			k=urm[k];
		
		if(P[k+1]==P[x])
			k++;
		
		urm[x]=k;
	}
}


int main()
{
	FILE *f=fopen("strmatch.in","r"), *g=fopen("strmatch.out","w");
	
fscanf(f,"%s",P);
fscanf(f,"%s",T);

n=strlen(T);
m=strlen(P);

urmatorul();

x=-1;
for(i=1;i<=m;i++)
	if(urm[i]==1)
		printf("%d ",i);
	
	for(i=0;i<n;i++)
	{
		if(x>-1 && P[x+1]!=T[i])
			x=urm[x];
		
		if(P[x+1]==T[i])
			x++;
		
		if(x==m-1)
		{
			nr++;
			if(nr<=1000)
			v[nr]=i-m+1;
			
		x=urm[x];
		}		
	}
fprintf(g,"%d\n",nr);
for(i=1;i<=minim(nr,1000);i++)
	fprintf(g,"%d ",v[i]);

fprintf(g,"\n");
	
fclose(f);

fclose(g);

	
	

return 0;
}