前回の説明

http://perogram.hateblo.jp/entry/rolling_hash
これでは通らない問題もあった（下記）
そこで、蟻本にならってh=2⁶⁴バージョンで書き直すとAC. 先人の知恵

Code

// ローリングハッシュ
// h = 2^64にすることでmod不要
using ull = unsigned long long;
vector<ll> rolling_hash_search(string s, string t){
    vector<ll> index_list;
    ll SL = s.size();
    ll TL = t.size();
    
    ull b = 1e8 + 7;

    // 蟻本でいう、bのm乗
    ull a = 1;
    FOR(i, 0, TL){
        a *= b;
    }
    
    // 先頭のローリングハッシュ
    ull s_hash = 0;
    FOR(i, 0, TL){
        s_hash = s_hash * b + s[i];
    }

    ull t_hash = 0;
    FOR(i, 0, TL){
        t_hash = t_hash * b + t[i];
    }

    // sの始点を1つずつ進めながらハッシュ値をチェック
    FOR(i, 0, SL - TL + 1){
        if(s_hash==t_hash){
            index_list.push_back(i);
        }

        if(i+TL<SL){
            s_hash = s_hash * b - s[i] * a + s[i+TL];
        }
    }

    return index_list;
}

Verify

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3586276#1