Cod sursa(job #293071)

Utilizator socheoSorodoc Ionut socheo Data 31 martie 2009 22:04:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
#include<string.h>
char a[2000004],b[2000004];
int i,km[2000004],nr,bun[1111],n,m;
void prefix()
{  km[1]=0;
int k=0;
 for(int y=2;y<=n;y++)
  { while(a[k+1]!=a[y]&&k>0)
       k=km[k];
    if(a[k+1]==a[y])
		k++;
	km[y]=k;
  }
}
void KMP()
{ prefix();
	int q=0;
for(int y=1;y<=m;y++)
 { while(b[y]!=a[q+1]&&q>0)
	 q=km[q];
   if(b[y]==a[q+1])
	   q++;
   if(q==n)
     { if(nr<=1000)
		 bun[nr]=y-n;
	   nr++;
	 }
 }	
}
int main()
{ freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",a);
scanf("%s",b);
n=strlen(a)-1;
m=strlen(b)-1;
nr=1;
for(i=n;i>=0;i--)
	a[i+1]=a[i];
a[0]=' ';
n++;
for(i=m;i>=0;i--)
	b[i+1]=b[i];
m++;
b[0]=' ';
KMP();
printf("%d\n",nr-1);
for(i=1;i<=nr-1&&i<=1000;i++)
	printf("%d ",bun[i]);
return 0;}