Cod sursa(job #1514700)

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