Cod sursa(job #2657502)

Utilizator Razvan11Rus Razvan Constantin Razvan11 Data 10 octombrie 2020 20:12:20
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <iostream>
#include <fstream>
using namespace std;

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

typedef long long LL;

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

/// Facem, mai intai, cu un singur hash.

LL rasp,v[m],j; /// Nr de potriviri
/// mai trebuie sa mai retin si pozitiile

int main()
{
    string a, b;

    fin >> a >> b;
    if( a .size() > b.size() )
        {
            cout << "Zero aparitii";
            return 0;
        }
     LL n = a.size(), i;
     LL vala = 0, valb = 0, put = 1;

     /// fac hash-ul primullui sir, cel pe care il caut
     for( i = 0; i < n; ++i )
         {
             vala = ( vala * baza + a[i]) % m;
             put = (put * baza );
         }
        ///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 n litere are hashul:" << valb << endl;

     if( vala == valb )
    {
        ++rasp;
        v[j++]=1;
    }



     /// 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 negative
         /// si sa ma gandesc la simetricul fata de adunare
        ///cout<<"valb = " << valb<<" ";
         LL ceva = (put * b[i-1]) % m ; /// l-am facut pozitiv
         valb = (  (valb - ceva)%m +m) % m;///ma gandesc daca scriu dir sau o alta var.
        ///cout << "ceva = " << ceva << endl;
        ///cout << "valb = " << valb << endl;
         if( vala == valb )
             {
                ///cout << "Potrivire pe poz " << i << endl;
                v[j++]=i;
                 ++rasp;
             }
     }
     gout <<rasp << endl;
     j=0;
    while(v[j])
        {
            gout<<v[j++]<<" ";
        }
    return 0;
}