Cod sursa(job #1838268)

Utilizator RaduhhRadu Flocea Raduhh Data 31 decembrie 2016 16:42:28
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>

#define baza 42
#define mod1 100007
#define mod2 100021

using namespace std;

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

string a,b,s;
int n,m,i,nr;
int hasha1,hasha2,hashb1,hashb2,hb1,hb2;

int main()
{
    fin>>a>>b;
    n=a.length();
    m=b.length();

    hb1=1;
    hb2=1;
    for (i=0; i<n; i++)
    {
        //Hashuim subsirul
        hasha1=(hasha1*baza+a[i]) % mod1;
        hasha2=(hasha2*baza+a[i]) % mod2;

        //Hashuim primele n caractere din sirul nostru
        hashb1=(hashb1*baza+b[i]) % mod1;
        hashb2=(hashb2*baza+b[i]) % mod2;

        if (i==0) continue;

        //Cream hashurile adaugatoare pentru sirul nostru
        hb1=(hb1*baza) % mod1;
        hb2=(hb2*baza) % mod2;
    }

    //Verificam daca hashurile coincid
    for (i=0; i<=m-n; i++)
    {
        if (hasha1==hashb1 && hasha2==hashb2) { nr++; s+=char(i+48); s+=" "; }

        //Eliminam primul caracter din hash-ul sirului nostru si adaugam urmatorul :
        hashb1=((hashb1 - (b[i]*hb1) % mod1 + mod1) * baza + b[i+n]) % mod1;
        hashb2=((hashb2 - (b[i]*hb2) % mod2 + mod2) * baza + b[i+n]) % mod2;
    }
    fout<<nr<<'\n'<<s;
    return 0;
}