Cod sursa(job #200077)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 22 iulie 2008 10:35:08
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#include <string.h>

#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define NMAX 2000010

int V[NMAX];
int k,h,q,i,n,m;
int pi[NMAX];
char A[NMAX],B[NMAX];

void read()

{

freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);

scanf("%s", A+1);
scanf("%s", B+1);

n=strlen(A-1);
m=strlen(B-1);
}

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

void KMP()
{
q=0;
h=0;
for (i=1;i<=m;i++)
     {
      while (q>0 && A[q+1]!=B[i])
	    q=pi[q];
	    if (A[q+1]!=B[i])
	       q++;
	       if (q==n)
		  {
		   h++;
		   q=pi[n];
		   if (h<=1000)
		      V[h]=i-n;
		      }
		   }
}

void print()
{
functia_prefix();
KMP();
printf("%d\n",h);
for (i=1;i<=h && i<=1000;i++)
printf("%d ",V[i]);
}

int main()
{
read();
print();
return 0;
}