Cod sursa(job #2509731)

Utilizator DysKodeTurturica Razvan DysKode Data 14 decembrie 2019 17:46:19
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

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

string s1, s2;
long long int hash_ref1, hash_ref2;
long long int hash_lim1 = 179365926438715;
long long int hash_lim2 = 124674293321839;
long long int hash_lim3 = hash_lim1 * 26;
long long int hash_lim4 = hash_lim2 * 26;
long long int h1, h2;
long long int elim1, elim2;
vector<int> v;
int main()
{
    fin >> s1 >> s2;
    elim1 = elim2 = 1;
    for(int i = 0 ; i < s1.length() ; i++)
    {
        hash_ref1 = (hash_ref1 * 26 + s1[i] - 'A') % hash_lim1;
        hash_ref2 = (hash_ref2 * 26 + s1[i] - 'A') % hash_lim2;
    }
    for(int i = 0 ; i < s1.length() - 1 ; i++)
    {
        elim1 = (elim1 * 26) % hash_lim1;
        elim2 = (elim2 * 26) % hash_lim2;
        h1 = (h1 * 26 + s2[i] - 'A') % hash_lim1;
        h2 = (h2 * 26 + s2[i] - 'A') % hash_lim2;
    }
    for(int i = s1.length() - 1 ; i < s2.length() ; i++)
    {
        h1 = (h1 * 26 + s2[i] - 'A') % hash_lim1;
        h2 = (h2 * 26 + s2[i] - 'A') % hash_lim1;
        if( h1 == hash_ref1 && h2 == hash_ref2 )
        {
            /// avem match
            if(v.size() < 1000)
                v.push_back( i - s1.length() + 1 );
        }
        int x = (s2[i - s1.length() + 1] - 'A');
        h1 = ( h1 - elim1 * x + hash_lim3 ) % hash_lim1;
        h2 = ( h2 - elim2 * x + hash_lim4 ) % hash_lim2;
    }
    fout << v.size() << '\n';
    for(auto it : v)
        fout << it << ' ';
}