Cod sursa(job #2684868)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 15 decembrie 2020 01:26:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
//Rabin-Karp

#include <iostream>
#include <fstream>
#include <cstring>

#define NMAX 2000002
using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int MOD1=1000007, MOD2=1000011;

char a[NMAX], b[NMAX];
int afis[NMAX];
int putere(int x, int e, int mod)
{
    if(e==0) return 1;
    if(e%2==0) return putere(1LL*x*x%mod, e/2, mod);
    return x*putere(1LL*x*x%mod, e/2, mod)%mod;
}
int main()
{
    int n, m, i, pow1, pow2, ha1=0, ha2=0, hb1=0, hb2=0, nr_afis=0;
    const int bz=123;
    fin.getline(a, NMAX); n=strlen(a);
    fin.getline(b, NMAX); m=strlen(b);

    for(i=0; i<n; i++)
    {
        hb1=(hb1*bz+b[i])%MOD1;
        hb2=(hb2*bz+b[i])%MOD2;
        ha1=(ha1*bz+a[i])%MOD1;
        ha2=(ha2*bz+a[i])%MOD2;
    }
    pow1=putere(bz, n-1, MOD1);
    pow2=putere(bz, n-1, MOD2);
    //sau
    if(ha1==hb1 && ha2==hb2) afis[++nr_afis]=0; //incepand cu pozitia 0
    for(i=n; i<m; i++)
    {
        hb1=((hb1%MOD1-1LL*b[i-n] * pow1 %MOD1+MOD1)%MOD1*bz+b[i])%MOD1;
        hb2=((hb2%MOD2-1LL*b[i-n] * pow2 %MOD2+MOD2)%MOD2*bz+b[i])%MOD2;
        //sau h=h % pow * pow+b[i];
        if(ha1==hb1 && ha2==hb2) afis[++nr_afis]=i-n+1;
    }
    fout<<nr_afis<<"\n";
    for(i=1; i<=nr_afis; i++) fout<<afis[i]<<' ';
}