Cod sursa(job #709581)

Utilizator Galax27Tapean Constantin Galax27 Data 8 martie 2012 11:55:51
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
#include<string.h>
#define mod1 1000013
#define mod2 1000029
#define baza 79
char a[2000000],b[2000000];
int n,m,i,j,v[2000000];
unsigned ha1,ha2,hb1,hb2,p1,p2;
int main()
{freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 scanf("%s %s",a,b);
 n=strlen(a);
 m=strlen(b);
 if(n>m)
   {printf("0");
    return 0;
   }
 for(i=0;i<=1000;i++)
  v[i]=-1;
 p1=p2=1;
 for(i=0;i<n;i++)
 {ha1=(ha1*baza+a[i])%mod1;
  ha2=(ha2*baza+a[i])%mod2;
  hb1=(hb1*baza+b[i])%mod1;
  hb2=(hb2*baza+b[i])%mod2;
  if(!i)
	 continue;
  p1=(p1*baza)%mod1;
  p2=(p2*baza)%mod2;
 } 
 for(i=0,j=1;i<m-n;i++)
 {if(ha1==hb1&&ha2==hb2)
    {v[0]++;
     v[j++]=i;
    }
  hb1=((hb1-(b[i]*p1)%mod1+mod1)*baza+b[i+n])%mod1;
  hb2=((hb2-(b[i]*p2)%mod2+mod2)*baza+b[i+n])%mod2;
 }
 printf("%d\n",++v[0]);
 for(i=1;(i<=1000)&&(v[i]!=-1);i++)
  printf("%d ",v[i]);
 fclose(stdin);
 fclose(stdout);
 return 0;
}