AOJ-ICPC 450 Substring

ロリハの練習問題として。

問題

Substring | Aizu Online Judge

制約

解法

ローリングハッシュ。となることを利用すると、各クエリに対してでハッシュが求まる。

前のハッシュに足したり引いたりで事足りるのでは？という考えも浮かぶが、ロリハは普通には割り算ができないことに注意(modを取っているので)。

Bの累乗を毎回計算していると間に合わないので、事前に計算しておく。↓のコードではダブリングを用いているが、せいぜい個なので全部計算しておいてもよい。

typedef unsigned long long ull;
const ull B = 100000007;
const int MAX_LOG = 50;

signed main() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<ull> H(n + 1);
    H[0] = 0;
    rep(i, n) {
        H[i + 1] = H[i] * B + s[i];
    }

    vector<ull> bb(MAX_LOG);
    bb[0] = B;
    rep(i, MAX_LOG - 1) {
        bb[i + 1] = bb[i] * bb[i];
    }

    set<ull> hash;
    int l = 1, r = 1;
    rep(i, m) {
        string q;
        cin >> q;
        if (q == "R++") {
            r++;
        } else if (q == "R--") {
            r--;
        } else if (q == "L++") {
            l++;
        } else if (q == "L--"){
            l--;
        }

        ull t = 1;
        ull e = r - l + 1;
        rep(i, MAX_LOG) {
            if (e & 1) {
                t *= bb[i];
            }
            e /= 2;
            if (e <= 0) break;
        }
        ull h = H[r] - t * H[l-1];
        hash.insert(h);
    }

    cout << hash.size() << endl;
}

使える技を増やしていかなきゃね。