Cod sursa(job #2679046)

Utilizator AlexNeaguAlexandru AlexNeagu Data 29 noiembrie 2020 14:27:18
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
const int hmod = 1e9 + 123;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

int mx_pow = 0, my_base;
int gen_base(const int before, const int after) {
    auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    std::mt19937 mt_rand(seed);
    int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
    return base % 2 == 0 ? base-1 : base;
}

struct p_hash {

    vector<int> pow1, pre1;
    vector<unsigned ll> pow2, pre2;
    int base, mx_pow;
    void assign_bases(int x, int y) {
        base = x;
        mx_pow = y;
    }
   
    void build(string s) {
        pre1.assign((int)s.size() + 1, 0);
        pre2.assign((int)s.size() + 1, 0);
        int n = s.size();
        //cout << base << '\n';
        pow1.push_back(1);
        pow2.push_back(1);
        while(pow1.size() <= n) {
            pow1.push_back( 1LL * pow1.back() * base % hmod);
            pow2.push_back(pow2.back() * base);
        }
        for(int i = 0; i < n; i++) {
            pre1[i + 1] = (pre1[i] + 1LL * (s[i] - 'A' + 1) * pow1[i]) % hmod;
            pre2[i + 1] = pre2[i] + (s[i] - 'A' + 1) * pow2[i];
        }
    }
    pair<int,unsigned long long> get(int pos, int len) {
        int hash1 = pre1[pos + len] - pre1[pos];
        unsigned long long hash2 = pre2[pos + len] - pre2[pos];
        if(hash1 < 0) hash1 += hmod;
        if(mx_pow > 0) {
            hash1 = 1ll * hash1 * pow1[mx_pow - (pos + len - 1)] % hmod;
            hash2 *= pow2[mx_pow - (pos + len - 1)];
        }
        return make_pair(hash1, hash2);
    }
};

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string s, t;
    in >> t >> s;
    mx_pow = max(s.size(), t.size());
    my_base = gen_base('z' - 'A' + 1, hmod);
    //poly_hash A, B;
    p_hash A, B;
    A.assign_bases(my_base, mx_pow);
    B.assign_bases(my_base, mx_pow);
    A.build(s);
    B.build(t);
    int cnt = 0;
    vector<int> ans;
    auto me = B.get(0, (int) t.size());
    for(int i = 0; i + (int) t.size() <= (int) s.size(); i++) {
        auto his = A.get(i, (int) t.size());
        //cout << me.first << ' ' << his.first << '\n';
        if(me == his && cnt < 1000) {
            ans.pb(i);
            if(cnt == 1000) break;
        }
    }
    out << ans.size() << '\n';
    for(auto it : ans) out << it << ' ';
    return 0;
}