Cod sursa(job #171248)

Utilizator kolapsysPostelnicu Dan Marian kolapsys Data 3 aprilie 2008 21:58:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
// http://infoarena.ro/problema/strmatch 
#include <stdio.h>
#include <string.h>

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

const int nmax = 2000100;
const int smax = 1009;

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 (v[0]<1000)
	    v[++v[0]] = i-a;
	 k = pi[k];
	}
    }
}

// ***** Sfarsit ***** //

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 <= v[0]; i++)
	fprintf(g, "%d ", v[i]);

 fclose(f); fclose(g);
 return 0;
}