Cod sursa(job #200079)

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

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

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

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

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

n=strlen(A+1);
m=strlen(B+1);

}

void prefix()
{
k=0;
pi[1]=0;
for (i=1;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()
{
k=0;
for (i=1;i<=m;i++)
    {
     while (k>0 && A[k+1]!=B[i])
	   k=pi[k];
	   if (A[k+1]==B[i])
	      ++k;
	      if (k==n)
		 {
		 ++nr;
		 k=pi[n];
		 if (nr<=1000)
		    V[nr]=i-n;
		    }
		}
}

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

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