Cod sursa(job #171007)

Utilizator kolapsysPostelnicu Dan Marian kolapsys Data 3 aprilie 2008 17:02:46
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
#include <string.h>

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

const int nmax=2000000;
const int smax=1000;

int r, a, b, v[smax], pi[nmax];

char A[nmax], B[nmax];

// ***** Algoritm Knuth Morris Pratt ***** //

void prefix()
{
 int k=0; pi[1]=0;
 for (int i=2; i<=a; i++)
    {
     while (k>0&&A[k+1]!=A[i])
		k=pi[k];
     if (A[k+1]==A[i]) pi[k]=k++;
    }
}

void kmp()
{
 int k=0;
 for (int i=1; i<=b; i++)
    {
     while (k>0&&A[k+1]!=B[i])
		k=pi[k];
     if (A[k+1]==B[i]) k++;
     if (k==a)
	{
	 r++;
	 if (r<1000)
	    v[r]=i-a;
	 k=pi[k];
	}
    }
}

// ***** Sfarsit ***** //
int min(int a,int b)
{
 if (a>b) return b;
 else return a;
}

int main()
{
 fscanf(f,"%s\n%s\n",&A,&B);
 a=strlen(A);
 b=strlen(B);

 prefix();

 kmp();

 fprintf(g,"%d",r);
 for(int i=1; i<=min(r,1000); i++)
	fprintf(g,"%d ",v[i]);
 return 0;
}