Cod sursa(job #709325)

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