Cod sursa(job #608963)

Utilizator ioana454Ioana S ioana454 Data 18 august 2011 20:54:02
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>
#include <string.h>
#define NMax 2000005

int NrAp=0;
int VcAp[1000];
int h=0;
char A[NMax],B[NMax];
int pi[NMax];
int m,n;


FILE *f,*g;


	
void prefix(char P[])
{
	int k=0,q;

	for( q=1,pi[1]=0;q<=m;q++)
	{
		while(k>0 &&P[k] != P[q])
			k=pi[k];
		if(P[k] == P[q])
			k=k+1;
		pi[q]=k;
	}

return;
}


void KMP(char P[], char T[])
{
	int q;

	prefix(P);

	q=0;
	for(int i=0;i<=n;i++)
	{
		while(q>0 && P[q] != T[i])
			q=pi[q];
	    if(P[q] == T[i])
			q=q+1;
		if(q==m)
		{
			VcAp[h++] = i-m+1;	
			q=pi[q-1];
			
		}
	}

}



int main()
{

	f=fopen("strmatch.in","r");
	g=fopen("strmatch.out","w");
	
	fgets(A, sizeof(A), f);
    fgets(B, sizeof(B), f);

	m=strlen(A);
	n=strlen(B);
	KMP(A,B);
	fprintf(g,"%d \n",h);
	for(int i=0;i<h;i++)
		fprintf(g,"%d ",VcAp[i]);
	
	scanf("%d");

	return 0;
}