Cod sursa(job #298151)

Utilizator katakunaCazacu Alexandru katakuna Data 5 aprilie 2009 21:26:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
using namespace std;
#include <cstdio>
#include <string.h>
#include <algorithm>

#define Nmax 2000010

int A, B, pi[Nmax], p, i, sol[1024];
char a[Nmax], b[Nmax];

void prefix(){

	int p = 0, i;
	for(i = 2; i <= A; i++){
		
		while( p && a[p + 1] != a[i])
			p = pi[p];
		
		if( a[p + 1] == a[i] ){
			p++;
			pi[i] = p;
		}
		
	}

}

int main(){

	FILE *f = fopen("strmatch.in", "r");
	FILE *g = fopen("strmatch.out", "w");

	a[0] = ' '; b[0] = ' ';
	fscanf(f,"%s",a + 1);
	fscanf(f,"%s",b + 1);
	A = strlen(a) - 1; B = strlen(b) - 1;
	
	prefix();
	
	p = 0;
	for(i = 1; i <= B; i++){
		
		while( p && b[i] != a[p+1] )
			p = pi[p];
		
		if( b[i] == a[p+1] ){
			p++;
			if(p == A)
				if(sol[0] <= 1000)
					sol[++sol[0]] = i - p;
				else
					++sol[0];
		}
		
	}
	
	fprintf(g,"%d\n",sol[0]);
	int M = min(sol[0], 1000);
	for(i = 1; i <= M; i++)
		fprintf(g,"%d ", sol[i]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}