Cod sursa(job #171092)

Utilizator kolapsysPostelnicu Dan Marian kolapsys Data 3 aprilie 2008 18:15:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <string.h>

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

const int nmax = 2000010;
const int smax = 1010;

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

char A[nmax], B[nmax];

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

void prefix()
{
 int k = 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[i] = ++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)
	{
	 ++nr;
	 if (nr<1000)
	    v[nr] = 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+1,B+1);
 a = strlen(A+1);
 b = strlen(B+1);

 prefix();

 kmp();

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