Cod sursa(job #1247949)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 24 octombrie 2014 12:57:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
#include <cstring>
#define z1 666013
#define z2  10003
#define p 83

using namespace std;
int i,n,m,k=0,K[1009],p1,p2,s1,s2,s3,s4,nr;
char a[2000009],b[2000009];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);


    gets(a);
    gets(b);

    m=strlen(a);
    n=strlen(b);
    p1=p2=1;
    s1=s2=s3=s4=0;

    for(i=0; i<m; ++i)
    {
        /////
        s1=( s1*p+a[i])%z1;
        s2=( s2*p+a[i])%z2;

        /////

        s3=( s3*p+b[i])%z1;
        s4=( s4*p+b[i])%z2;

        /////
        if(i!=0)
        {
            p1=p1*p%z1;
            p2=p2*p%z2;
        }

    }

    nr=0;

    if(s1==s3 && s2==s4)
    {
        ++nr;
        K[++k]=0;
    }

    for(i=m; i<n; ++i)
    {
        s3=( ( (s3-p1*b[i-m])%z1+z1) *p+b[i])%z1;
        s4=( ( (s4-p2*b[i-m])%z2+z2) *p+b[i])%z2;

       if(s1==s3 && s2==s4)
        {
            ++nr;
            if(k<1000) K[++k]=i-m+1;
        }


    }

    printf("%d\n",nr);

    for(i=1; i<=k; ++i)
        printf("%d ",K[i]);




    return 0;
}