Cod sursa(job #2312825)

Utilizator BungerNadejde George Bunger Data 5 ianuarie 2019 16:10:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int NMAX=2e6+5,MOD=1e5+21,BAZA=75;
char c[NMAX],t[NMAX];
vector <int> v;
int putere=1,lc,lt,valCuv,valHash;

void citire()
{
    fin>>c>>t;
}

void RabinKarp()
{
    lc=strlen(c);
    lt=strlen(t);
    for(int i=1; i<=lc-1 ; i++)
        putere=putere*BAZA%MOD;

    valCuv=0;
    for(int i=0; i<lc; i++)
    {
        valCuv=(valCuv*BAZA)%MOD+(c[i]-'0')%MOD;
        valCuv=valCuv%MOD;
    }

    valHash=0;
    for(int i=0; i<lc; i++)
    {
        valHash=(valHash*BAZA)%MOD+(t[i]-'0')%MOD;
        valHash=valHash%MOD;
    }

    if(valCuv==valHash)
        v.push_back(0);

    for(int i=lc; i<lt; i++)
    {
        valHash=(((valHash-putere*(t[i-lc]-'0'))%MOD+MOD)*BAZA+(t[i]-'0'))%MOD;
        if(valHash==valCuv)
            v.push_back(i-lc+1);
    }
}

void afisare()
{
    int q=v.size();
    fout<<q<<'\n';
    for(int i=0; i<min(q,1000); i++)
        fout<<v[i]<<" ";
}

int main()
{
    citire();
    RabinKarp();
    afisare();
    return 0;
}