Cod sursa(job #1251470)

Utilizator savulescustefanSavulescu Stefan savulescustefan Data 29 octombrie 2014 16:03:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#include <cstring>
using namespace std;
int p1,p2,q1,q2,q11,q22,p11,p22,c[1004],nr,r,n,i,p;
char x,a[2000004],b[2000004];
int main()
{

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