Cod sursa(job #200087)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 22 iulie 2008 11:10:25
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>
#include <cstring>
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define NMAX 2000010
#define NMIN 1001

char A[NMAX], B[NMAX];
long n,m;
long pi[NMAX],i,k;
long V[NMAX];
long nr;
long X[NMIN];
  

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

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

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

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

//KMP
k=0;
for (i=1; i<=m; ++i) {
    while (A[k+1]!=B[i] && k>0) k=pi[k];
    if (A[k+1]==B[i])
	++k;
	if (k==n)
	   {
	    ++nr;
	 if (X[0]<1000)
	    X[++X[0]]=i-n;
	}
    }
  
printf("%ld\n",nr);
for (i=1; i<=X[0];++i)
    printf("%ld ",X[i]);
return 0;
}