Cod sursa(job #2922867)

Utilizator Paul_DobrescuPaul Dobrescu Paul_Dobrescu Data 10 septembrie 2022 13:46:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
 
ifstream reader ("strmatch.in");
ofstream writer ("strmatch.out");
 
const ll mod1 = 1e9 + 7;
const ll mod2 = 1e9 + 9;
const ll baza = 73;
 
 
int main()
{
// #ifndef ONLINE_JUDGE
//     freopen("input", "r", stdin);
//     freopen("output", "w", stdout);
// #endif
    string a, b;
    reader >> a >> b;
 
    if(b.size() < a.size())
    {
        writer << 0;
        return 0;
    }
 
    pair <ll, ll> hashA;
 
    for(auto it : a)
    {
        hashA.first = (hashA.first * 1LL * baza + it) % mod1;
        hashA.second = (hashA.second * 1LL * baza + it) % mod2;
    }
   // cout << hashA.first << " " << hashA.second << '\n';
 
    pair <ll, ll> hashB;
 
    for(int i = 0; i < a.size(); ++i)
    {
        hashB.first = (hashB.first * 1LL * baza + b[i]) % mod1;
        hashB.second = (hashB.second * 1LL * baza + b[i]) % mod2;
    }
 
   // cout << hashB.first << " " << hashB.second << '\n';
 
 
    vector <ll> matches;
 
    if(hashA == hashB)
        matches.emplace_back(0);
 
    pair<ll, ll> val = {1, 1};
    for(int i = 0; i <= a.size() - 2; ++i)
    {
        val.first = (val.first * 1ll * baza) % mod1;
        val.second = (val.second * 1ll * baza) % mod2;
    }
 
    //cout << "val : " << val.first << " " << val.second << '\n';
    
    int nrMatches = matches.size();

    for(int i = a.size(); i < b.size(); ++i)
    {
        hashB.first = (((hashB.first * 1LL - (b[i - a.size()] * 1LL * val.first) % mod1) % mod1 + mod1) % mod1 * 1LL * baza + b[i]) % mod1;
 
        hashB.second = (((hashB.second * 1LL - (b[i - a.size()] * 1LL * val.second) % mod2) % mod2 + mod2) % mod2 * 1LL * baza + b[i]) % mod2;
 
        //cout << i - a.size() + 1 << ": "<< hashB.first << " " << hashB.second << '\n';
    

        if(hashA == hashB)
        {
            nrMatches++;
            if(matches.size() < 1000)
                matches.emplace_back(i - a.size() + 1);
        }
    }
 
    writer<< nrMatches << '\n';
    for(auto it : matches)
        writer << it << " "; 
    return 0;
}