Cod sursa(job #2657720)

Utilizator Nico10Nicola Andrei George Nico10 Data 11 octombrie 2020 18:44:02
Problema Potrivirea sirurilor Scor 22
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <vector>
using namespace std;

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

const LL baza=10007;
const LL m=10037;

LL rasp;
vector<LL> v;
int main()
{
    string a, b;
    fin>>a>>b;
    if( a.size() > b.size() )
    {
        fout<<"Zero aparitii";
        return 0;
    }

    LL n = a.size(), i;
    LL vala = 0, valb = 0, put=1;

    ///fac hash-ul primului sir, cel pe care il caut
    for(i = 0; i < n; i++)
    {
        vala = (vala * baza + a[i] ) % m;
        put = (put * baza) % m;
    }
    //@cout<<"hash("<<a<<")="<<vala<<endl;
    ///Il fac pe al doilea
    for(i = 0; i < n; i++)
        valb = (valb * baza + b[i] ) % m;
    //cout<<"Primul grup de litere are hashul: "<<valb<<endl;

    if( vala == valb ) ++rasp;

    ///scad dimensiunea sirului cautat deoarece altfel as iesi cu o
    ///bucata din sirul mic in exteriorul/in dreapta sirului mare
    for(i = 1; i <= b.size() - n; ++i){
        valb = (valb * baza + b[i+n-1] ) % m;

        ///Fac smecheria de care va spuneam, adun nr prim m, ca sa nu am
        ///nr neg si sa ma gandesc la simetricul fata de adunare

        LL ceva = (put * b[i-1]) % m;
        valb = ( valb - ceva + m) % m;

        ///cout<<"valb="<<valb<<endl;
        ///cin.get();

        ///put = (put + baza) % B;
        if( vala == valb ){
            ///cout<<" Potrivire pe poz: "<< i << endl;
            ///cout<<"v.size()="<<v.size()<<"\n";
            ++rasp;
            ///if( v.size() < 1000 )
            v.push_back( i );
        }

    }
    ///Nr potriviri =
    fout << rasp << "\n";
    for( i = 0; i < v.size(); ++i )
        fout<<v[i]<<" ";
    return 0;
}