test/yosupo-zalgo-rollinghash.test.cpp

• View this file on GitHub
• Last update: 2025-04-28 15:10:34+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• string/rolling-hash.cpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <bits/stdc++.h>
using namespace std;

#include "../string/rolling-hash.cpp"

int main() {
    string s;
    cin >> s;
    int n = (int)s.size();

    RollingHash rh;
    auto hashed = rh.build(s);

    for(int i = 0; i < n; i++) {
        int ok = 0, ng = n - i + 1;
        while(ng - ok > 1) {
            int mid = (ok + ng) / 2;
            if(rh.slice(hashed, 0, mid) == rh.slice(hashed, i, i + mid))
                ok = mid;
            else
                ng = mid;
        }

        cout << ok << " \n"[i + 1 == n];
    }
}

#line 1 "test/yosupo-zalgo-rollinghash.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/zalgorithm"

#include <bits/stdc++.h>
using namespace std;

#line 2 "string/rolling-hash.cpp"

#line 4 "string/rolling-hash.cpp"
using namespace std;

class RollingHash {
private:
    const uint64_t MOD = (1ull << 61) - 1;
    vector<uint64_t> power{1};
    uint64_t base = 0;

    uint64_t mul(__uint128_t l, __uint128_t r) {
        __uint128_t t = l * r;
        t = (t >> 61) + (t & MOD);
        return t < MOD ? t : t - MOD;
    }
    uint64_t get_base() {
        random_device engine;
        uniform_int_distribution<uint64_t> dist(129, MOD - 1);
        return dist(engine);
    }
    uint64_t pow(size_t p) {
        if(power.size() <= p) {
            size_t sz = power.size();
            power.resize(p + 1);
            while(sz <= p) {
                power[sz] = mul(power[sz - 1], base);
                sz++;
            }
        }
        return power[p];
    }

public:
    explicit RollingHash() : base(get_base()) {}
    vector<uint64_t> build(const string &s) {
        vector<uint64_t> hashed(s.size() + 1);
        for(size_t i = 0; i < s.size(); i++) {
            hashed[i + 1] = mul(hashed[i], base) + s[i];
            if(hashed[i + 1] >= MOD) hashed[i + 1] -= MOD;
        }
        return hashed;
    }
    uint64_t slice(const vector<uint64_t> &hashed, size_t l, size_t r) {
        uint64_t res = hashed[r] + MOD - mul(hashed[l], pow(r - l));
        return res < MOD ? res : res - MOD;
    }
};
#line 7 "test/yosupo-zalgo-rollinghash.test.cpp"

int main() {
    string s;
    cin >> s;
    int n = (int)s.size();

    RollingHash rh;
    auto hashed = rh.build(s);

    for(int i = 0; i < n; i++) {
        int ok = 0, ng = n - i + 1;
        while(ng - ok > 1) {
            int mid = (ok + ng) / 2;
            if(rh.slice(hashed, 0, mid) == rh.slice(hashed, i, i + mid))
                ok = mid;
            else
                ng = mid;
        }

        cout << ok << " \n"[i + 1 == n];
    }
}

Back to top page