Cod sursa(job #1251432)

Utilizator savulescustefanSavulescu Stefan savulescustefan Data 29 octombrie 2014 14:37:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <cstdio>

using namespace std;
int p1,p2,q1,q2,q11,q22,p11,p22,a[2000004],b[2000004],c[1004],nr,r,n,i,p;
char x;
int main()
{

    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    scanf ("%c", &x);
    while (x!='\n')
    {
        a[++nr]=int(x);
        scanf ("%c", &x);
    }
    scanf ("%c", &x);
    while (x!='\n')
    {
        b[++r]=int(x);
        scanf ("%c", &x);
    }
    p=131;
    for (i=1;i<=nr;i++)
    {
        q1*=p;
        q1+=a[i];
        q1%=666013;
        q2*=p;
        q2+=a[i];
        q2%=10003;
    }
    p1=1;
    p2=1;
    for (i=1;i<=nr;i++)
    {
        q11*=p;
        q11+=b[i];
        q11%=666013;
        q22*=p;
        q22+=b[i];
        q22%=10003;
        if (i>1)
        {
        p1*=p;
        p1%=666013;
        p2*=p;
        p2%=10003;
        }
    }
    if (q11==q1 && q22==q2)
        c[++n]=0;
    for (i=nr+1;i<=r;i++)
    {
        q11-=(p1*b[i-nr]);
        q22-=(p2*b[i-nr]);
        q11%=666013;
        q22%=10003;
        if (q11<0)
            q11+=666013;
        if (q22<0)
            q22+=10003;
        q11*=p;
        q11%=666013;
        q22*=p;
        q22%=10003;
        q11+=b[i];
        q22+=b[i];
        q11%=666013;
        q22%=10003;
        if (q11==q1 && q22==q2)
        {
            if (n>=999)
            n++;
            else
            c[++n]=i-nr;
        }
    }
    printf ("%d\n", n);
    for (i=1;i<=n && i<=1000;i++)
        printf ("%d ", c[i]);
    return 0;
}