Cod sursa(job #1514689)

Utilizator ipus1Stefan Enescu ipus1 Data 31 octombrie 2015 14:07:10
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<cstdio>
#include<cstring>
#define n1 2000003
#define n2 2000017
char v[2000001],v2[2000001],sol[1001];
int main ()
{freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
int k1,k2,i,m1,m2,p1,p2,x1,x2,q=0;
scanf("%s%s",&v,&v2);
k1=strlen(v);
k2=strlen(v2);
x1=x2=1;
m1=0;
m2=0;
for(i=0;i<=k1-1;i++)
    {m1=(m1*123+v[i])%n1;
    m2=(m2*123+v[i])%n2;
    }
p1=0;
p2=0;
for(i=0;i<=k1-1;i++)
    {p1=(p1*123+v2[i])%n1;
    p2=(p2*123+v2[i])%n2;
    }
x1=x2=1;
for(i=1;i<k1;i++)
    {x1=(x1*123)%n1;
    x2=(x2*123)%n2;
    }
if(k1>k2)
    {printf("0");
    return 0;
    }
if(m1==p1&&m2==p2)
    {q=1;
    sol[1]=0;
    }
for(i=k1;i<k2;i++)
    {p1=((p1-(v2[i-k1]*x1)%n1+n1)*123+v2[i])%n1;
    p2=((p2-(v2[i-k1]*x2)%n2+n2)*123+v2[i])%n2;
    if(m1==p1&&m2==p2)
        {q++;
        if(q<=1000)
            sol[q]=i-k1+1;
        }
    }
printf("%d\n",q);
for(i=1;i<=q;i++)
    printf("%d ",sol[i]);
return 0;
}