Cod sursa(job #200088)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 22 iulie 2008 11:15:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <string.h>
  
const long MAX=2000010;
char A[MAX],B[MAX];
long n,m;   
long pi[MAX],i,k;   
long nr,X[1001];
  
int main()
{
freopen("strmatch.in","rt",stdin);
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;
	}
    }
freopen("strmatch.out","wt",stdout);
printf("%ld\n", nr);
for (i=1; i<=X[0]; ++i)
printf("%ld ",X[i]);
return 0;
}