Cod sursa(job #584447)

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


int n,m,urm[dim],nr,v[1001],x,i,k;
char T[dim],P[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=0;i<n;i++)
	{	
		while(x>-1 && P[x+1]!=T[i])
			x=urm[x];
		
		if(P[x+1]==T[i])
			x++;	//s-au potrivit
		
		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;
}