Cod sursa(job #1867495)

Utilizator smatei16Matei Staicu smatei16 Data 4 februarie 2017 10:13:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <cstring>
#define mod 66013
#define mod1 10013
#define b1 27
#define b2 29
using namespace std;
char a[2000003],b[2000003];
int i,h1,h2,v1,v2,nr,c[1003],n,m,x,y,p,p1;
int main()
{freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",&a,&b);
for(i=0;i<strlen(a);i++){
h1=(h1*b1+(int)a[i])%mod;
h2=(h2*b2+(int)a[i])%mod1;
v1=(v1*b1+(int)b[i])%mod;
v2=(v2*b2+(int)b[i])%mod1;
}
if(v1==h1 && v2==h2){
nr++;
c[nr]=0;
}
p=p1=1;
m=strlen(a);n=strlen(b);
for(i=0;i<m-1;i++){
p=(p*b1)%mod;
p1=(p1*b2)%mod1;
}
for(i=m;i<n;i++){
x=(int)b[i-m];y=(int)b[i];
v1=((v1-(x*p)%mod+mod)*b1+y)%mod;
v2=((v2-(x*p1)%mod1+mod1)*b2+y)%mod1;
if(v1==h1 && v2==h2){nr++;
if(nr<1000)
c[nr]=i-strlen(a)+1;}
}

printf("%d\n",nr);
for(i=1;i<=nr;i++)printf("%d ",c[i]);
    return 0;
}