test/RollingHash.test.cpp

• View this file on GitHub
• Last update: 2021-09-12 23:44:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B

Depends on

• Rolling Hash (mod 2^61-1) (string/RollingHash.cpp)
• template/template.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B"

#include "../string/RollingHash.cpp"

int main(){
    string S,T;
    cin>>S>>T;
    RollingHash<string>RH1(S),RH2(T);
    rep(i,len(S)-len(T)+1){
        if(RH1.get(i,i+len(T))==RH2.hash[len(T)])cout<<i<<"\n";
    }
}

#line 1 "test/RollingHash.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_14_B"

#line 2 "template/template.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, n) for (int i = 1; i < n; i++)
#define rev(i, n) for (int i = n - 1; i >= 0; i--)
#define REV(i, n) for (int i = n - 1; i > 0; i--)
#define all(v) v.begin(), v.end()
#define PL pair<ll, ll>
#define PI pair<int, int>
#define pi acos(-1)
#define len(s) (int)s.size()
#define compress(v) \
    sort(all(v));   \
    v.erase(unique(all(v)), v.end());
#define comid(v, x) lower_bound(all(v), x) - v.begin()

template<class T>
using prique=priority_queue<T,vector<T>,greater<>>;

template <class T, class U>
inline bool chmin(T &a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
constexpr ll inf = 3e18;
#line 3 "string/RollingHash.cpp"

template <class T>
struct RollingHash {
    ll Base = 283;
    const ll MASK30 = (1ll << 30) - 1;
    const ll MASK31 = (1ll << 31) - 1;
    const ll MOD = (1ll << 61) - 1;
    vector<ll> hash, power;
    ll calcmod(ll v) {
        v = (v & MOD) + (v >> 61);
        if (v > MOD) v -= MOD;
        return v;
    }
    ll mul(ll x, ll y) {
        ll xu = x >> 31, xd = x & MASK31;
        ll yu = y >> 31, yd = y & MASK31;
        ll mid = xd * yu + xu * yd, midu = mid >> 30, midd = mid & MASK30;
        return calcmod(xu * yu * 2 + midu + (midd << 31) + xd * yd);
    }
    RollingHash(T s) {
        ll sz = s.size();
        hash.resize(sz + 1, 0);
        power.resize(sz + 1, 1);
        rep(i, sz) {
            hash[i + 1] = calcmod(mul(hash[i], Base) + s[i]);
            power[i + 1] = calcmod(mul(power[i], Base));
        }
    }
    ll get(ll l, ll r) {
        return calcmod(hash[r] - mul(hash[l], power[r - l]) + MOD);
    }
    ll lcp(ll x, ll y) {
        ll len = min(hash.size() - 1 - y, hash.size() - 1 - x);
        ll ok = 0, ng = len + 1;
        while (ng - ok > 1) {
            ll mid = (ok + ng) / 2;
            if (get(x, x + mid) == get(y, y + mid))
                ok = mid;
            else
                ng = mid;
        }
        return ok;
    }
};
/*
@brief Rolling Hash (mod 2^61-1)
@docs docs/RollingHash.md
*/
#line 4 "test/RollingHash.test.cpp"

int main(){
    string S,T;
    cin>>S>>T;
    RollingHash<string>RH1(S),RH2(T);
    rep(i,len(S)-len(T)+1){
        if(RH1.get(i,i+len(T))==RH2.hash[len(T)])cout<<i<<"\n";
    }
}

Back to top page