Cod sursa(job #1535603)

Utilizator aetherAlexandra Vanca aether Data 24 noiembrie 2015 22:58:11
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
# include <fstream>
# include <iostream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int expo(int baza, int putere, int M)
{
    int rez=1, power=baza, exp=putere;
    while (exp)
    {
        if (exp&1)
            rez=(1LL*rez*power)%M;
        power=(1LL*power*power)%M;
        exp>>=1;
    }
    return rez;
}
char a[2000001], b[2000001], v[1001];
int main()
{
    int i=0, la=0, ha1=0, ha2=0, hb1=0, hb2=0, d=0, index=0;
    int M1=100129, M2=99923;
    f>>a>>b;
    for (i=0; a[i]; i++)
    {
        ha1=(ha1*257+a[i])%M1;
        ha2=(ha2*257+a[i])%M2;
        la++;
    }
    for (i=0; i<la; i++)
    {
        hb1=(hb1*257+b[i])%M1;
        hb2=(hb2*257+b[i])%M2;
    }
    if (ha1==hb1 && ha2==hb2)
    {
        d++;
        v[index]='0';
        v[++index]=' ';
        index++;
    }
    for (i=la; b[i]; i++)
    {
        int put1=expo(257, la, M1)%M1;
        int put2=expo(257, la, M2)%M2;
        hb1=((hb1*257+b[i])%M1 - (b[i-la]*put1)%M1 + M1)%M1;
        hb2=((hb2*257+b[i])%M2 - (b[i-la]*put2)%M2 + M2)%M2;
        if (hb1==ha1 && hb2==ha2)
        {
            d++;
            if (d<=1000)
            {
                v[index]='0'+i-la+1;
                v[++index]=' ';
                index++;
            }
        }
    }

    g<<d<<'\n';
    g<<v;

    return 0;
}