Cod sursa(job #390499)

Utilizator BaduBadu Badu Badu Data 3 februarie 2010 21:05:30
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<cstdio>
#include<string.h>
#define max 2000001

char t[max],p[max];
int ant[max],n,m;
int poz[1001];

void prefix(){
	
	int k,i;k=-1;
	poz[0]=0;
	for( i=1; i<m;i++){
		
		while( k>0 && p[k+1] != p[i] ) k = ant[k];
		
		if( p[k+1] == p[i] ) k++;
		ant[i] = k;
	}
}

int main(){
	
	FILE *f=fopen("strmatch.in","r");
	FILE *g=fopen("strmatch.out","w");
	
	int x = -1;int k=0;
	
	fscanf(f,"%s\n%s",p,t);
	
	m = strlen(p);
	n = strlen(t);
	
	prefix();
	
	int i;
	
	for(i=0; i<n;i++){
		
		while( x>0 && p[ x+1 ] != t[i] ) x = ant[x];
		
		if( p[x+1] == t[i] ) x++;
		if( x == m-1 ){ k++; if( k<1001 ) poz[k] = i-m+1; x = ant[x]; }
		
	}
	
	fprintf(g,"%d\n",k);
	if( k>1000 ) k=1000;
	for(i=1;i<=k;i++) fprintf(g,"%d ",poz[i]);
	
	return 0;
}