Cod sursa(job #355903)

Utilizator marinMari n marin Data 12 octombrie 2009 16:58:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#include <string.h>
#define DIM 2000002

char A[DIM];
char B[DIM];
int P[DIM];

int S[1002];

int dA, dB, i, k, sol;

int main(){
	FILE *f = fopen("strmatch.in","r");
	fscanf(f,"%s",A);
	fscanf(f,"%s",B);
	fclose(f);
	
	for (i = dA = strlen(A); i>0; i--)
		A[i] = A[i-1];
	
	for (i = dB = strlen(B); i>0; i--)
		B[i] = B[i-1];
	
	
	//fac prefix pentru A (subsirul)
	//P[i] = cel mai lung prefix care este si dufix ce se termina pe pozitia i
	
	P[1] = 0;
	for (i=2, k=0;i<=dA;i++) {
		while (A[i] != A[k+1] && k>0)
			k = P[k];
		if (A[i] == A[k+1]) {
			k++;
			P[i] = k;
		}/* else
			P[i] = 0;*/
	}
	
	for (i=1,k=0;i<=dB;i++) {
		while (k && B[i]!=A[k+1])
			k = P[k];
		if (B[i] == A[k+1]) {
			k++;
			if (k == dA) {
				sol++;
				if (sol <= 1000)
				S[sol] = i-dA;
			}
		}
	}
		
	FILE *g = fopen("strmatch.out","w");
	fprintf(g,"%d\n",sol);
	if (sol>1000)
		sol = 1000;
	for (i = 1;i<=sol;i++)
		fprintf(g,"%d ",S[i]);
	fclose(g);
	
	return 0;
}