Cod sursa(job #2657088)

Utilizator TheRealInfiniteConstantin Alexandru TheRealInfinite Data 9 octombrie 2020 17:27:04
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

typedef long long LL;

const LL baza = 99991;
const LL m = 10037;

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

LL rasp; /// Nr de potriviri
vector<LL> v;/// mai trebuie sa mai retin si pozitiile

int main()
{
    string a, b;

    f >> a >> b;
    if( a .size() > b.size() )
        {
            g<<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;
         }
     /// Il fac pe al doilea
      for( i = 0; i < n; ++i )
         valb = ( valb * baza + b[i] ) % m;

     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

         LL ceva = (put * b[i-1]) % m + m; /// l-am facut pozitiv
         valb = ((valb - ceva ) % m + m) % m; ///ma gandesc daca scriu dir sau o alta var.

         ///put = (put * baza) % B;
         if( vala == valb)
             {
                 ++rasp;
                 if(v.size() < 1000)
                    v.push_back(i);
             }
     }

    g<<rasp<<endl;

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

    return 0;
}