Cod sursa(job #2657515)

Utilizator Razvan11Rus Razvan Constantin Razvan11 Data 10 octombrie 2020 20:34:36
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include <iostream>
#include <fstream>
#include <vector>
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; /// Nr de potriviri
/// mai trebuie sa mai retin si pozitiile
vector<LL>v;

int main()
{
    string a, b;

    fin >> a >> b;
    if( a .size() > b.size() )
        {
            gout <<0;
            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 )%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 n litere are hashul:" << valb << endl;

     if( vala == valb )
    {
        ++rasp;
         v.push_back(0);
    }



            /// 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 )
             {
                ++rasp;
                ///cout << "Potrivire pe poz " << i << endl;
                if(v.size() < 1000)
                    v.push_back(i);

             }
     }
     gout <<rasp << endl;

    for(int j = 0; j < v.size(); j++)
        {
            gout<<v[j]<<" ";
        }
    return 0;
}