Cod sursa(job #2702388)

Utilizator BereaBerendea Andrei Berea Data 3 februarie 2021 20:48:33
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>

using namespace std;
const unsigned long long int base=1010012383;
const unsigned long long int mod=1010012359;
long long int hasha,hashb;    // astea sunt hash-urile
long long int plm,pow;
int i;
int c=0;       // numarul de secvente gasite
string a,b;
vector<int>v;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int main()
{
    cin>>a>>b;
    pow=1;
    if (a.size()>b.size()) // daca sirul a este mai lung ca b
    {
        cout<<0;
        return 0;
    }
    for (i=0;i<a.size();i++) // se face hasu-ul lui a
    {
        hasha=(hasha*base+a[i])%mod;
        pow=(pow*base)%mod;
    }
    for (i=0;i<a.size();i++) // se face prima partehash-ul lui b
    {
        hashb=(hashb*base+b[i])%mod;
    }
    if (hasha==hashb)
    {
        if (v.size()<1000) v.push_back(0);
        c++;
    }
    for (i=1;i<b.size()-a.size();i++)  // scad dimensiunea sirului cautat pentru a nu ajunge in exteriorul sirului cautat, in dreapta
    {
        hashb=(hashb*base+b[i+a.size()-1])%mod;
        plm=(pow*b[i-1])%mod;
        hashb=(hashb-plm+mod)%mod;
        if (hasha==hashb)
        {
            if (v.size()<1000) v.push_back(i);
            c++;
        }
    }
    cout<<c<<"\n";
    for (i=0;i<v.size();i++) cout<<v[i]<<" ";
}