Day 022-Q4 | 多項式ハッシュと文字列の高速照合

問題

長さ $N$ の文字列 $S$ と $Q$ 個のクエリが与えられる。各クエリは以下のいずれか:

クエリ 1 l r x: $S$ の $[l, r]$（1-indexed, 閉区間）の部分文字列を文字列 $x$ に変更する（$|x| = r - l + 1$）
クエリ 2 l1 r1 l2 r2: 部分文字列 $S[l1..r1]$ と $S[l2..r2]$ が等しいか判定する
クエリ 3 p t: パターン $t$ が $S[p..]$ に含まれるか、最初の出現位置を答える（なければ -1）

入力形式

N Q
S
クエリ1
クエリ2
...
クエリQ

制約

$1 \leq N \leq 3 \times 10^5$

$1 \leq Q \leq 2 \times 10^5$

$S$, $x$, $t$ は英小文字のみ

クエリ3: $|t| \leq 10^4$

入出力例

入力例 1

7 4
abcabcd
2 1 3 4 6
1 4 6 xyz
2 1 3 4 6
3 1 ab

出力例 1

Yes
No
1

ヒント (段階的開示)

ヒント1: 方向性

クエリ2は Rolling Hash で $O(1)$ 比較。クエリ3は Z-algorithm または KMP で $O(|t| + |S|)$。クエリ1の更新後にハッシュを再構築するか、Segment Tree 上でハッシュを管理する。

ヒント2: アプローチ

文字列比較（クエリ2）: セグメント木でハッシュを管理。各ノードに区間ハッシュを保持し、更新 $O(\log N)$、クエリ $O(\log N)$。
パターン検索（クエリ3）: concat(t, '$', S[p:]) に Z-algorithm を適用し、$Z[i] \geq |t|$ となる最小 $i$ を探す。

ヒント3: 誘導

MOD1 = (1 << 61) - 1  # Mersenne prime
BASE1 = 131

class HashSegTree:
    def __init__(self, s):
        self.n = len(s)
        self.pow_base = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.pow_base[i] = self.pow_base[i-1] * BASE1 % MOD1
        # Build segment tree
        ...

    def _pull(self, i):
        l, r = 2*i, 2*i+1
        self.length[i] = self.length[l] + self.length[r]
        self.tree[i] = (self.tree[l] * self.pow_base[self.length[r]] + self.tree[r]) % MOD1

模範解答 (Python)

import sys
input = sys.stdin.readline

MOD = (1 << 61) - 1
BASE = 131

def mul(a, b):
    return a * b % MOD

class HashSegTree:
    def __init__(self, s):
        n = len(s)
        self.n = n
        self.pw = [1] * (n + 1)
        for i in range(1, n + 1):
            self.pw[i] = self.pw[i-1] * BASE % MOD

        self.sz = 1
        while self.sz < n:
            self.sz <<= 1

        self.h = [0] * (2 * self.sz)
        self.ln = [0] * (2 * self.sz)

        for i, c in enumerate(s):
            self.h[self.sz + i] = ord(c) - ord('a') + 1
            self.ln[self.sz + i] = 1

        for i in range(self.sz - 1, 0, -1):
            self._up(i)

    def _up(self, i):
        l, r = 2*i, 2*i+1
        self.ln[i] = self.ln[l] + self.ln[r]
        self.h[i] = (self.h[l] * self.pw[self.ln[r]] + self.h[r]) % MOD

    def update(self, pos, c):  # 0-indexed
        i = self.sz + pos
        self.h[i] = ord(c) - ord('a') + 1
        i >>= 1
        while i >= 1:
            self._up(i)
            i >>= 1

    def query(self, l, r):  # [l, r] 0-indexed, returns hash
        hl, hr = 0, 0
        ll, lr = 0, 0
        l += self.sz
        r += self.sz + 1
        while l < r:
            if l & 1:
                hl = (hl * self.pw[self.ln[l]] + self.h[l]) % MOD
                ll += self.ln[l]
                l += 1
            if r & 1:
                r -= 1
                hr = (self.h[r] * self.pw[lr] + hr) % MOD
                lr += self.ln[r]
            l >>= 1
            r >>= 1
        return (hl * self.pw[lr] + hr) % MOD

def z_function(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    l, r = 0, 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

def main():
    N, Q = map(int, input().split())
    S = list(input().strip())

    seg = HashSegTree(S)

    results = []
    for _ in range(Q):
        line = input().split()
        tp = int(line[0])

        if tp == 1:
            l, r = int(line[1]) - 1, int(line[2]) - 1
            x = line[3]
            for i, c in enumerate(x):
                S[l + i] = c
                seg.update(l + i, c)

        elif tp == 2:
            l1, r1 = int(line[1]) - 1, int(line[2]) - 1
            l2, r2 = int(line[3]) - 1, int(line[4]) - 1
            h1 = seg.query(l1, r1)
            h2 = seg.query(l2, r2)
            results.append("Yes" if h1 == h2 else "No")

        else:  # tp == 3
            p = int(line[1]) - 1  # 0-indexed
            t = line[2]
            # Concatenate t + '$' + S[p:]
            combined = t + '$' + ''.join(S[p:])
            z = z_function(combined)
            lt = len(t)
            ans = -1
            for i in range(lt + 1, len(combined)):
                if z[i] >= lt:
                    pos_in_s = p + (i - lt - 1)
                    ans = pos_in_s + 1  # 1-indexed
                    break
            results.append(ans)

    print('\n'.join(map(str, results)))

main()

Step-by-Step 解説

1ハッシュセグメント木
各ノードが区間ハッシュ $H(l, r) = \sum_{i=l}^{r} s_i \cdot B^{r-i} \pmod{M}$ を保持。結合: $H(l, r) = H(l, m) \cdot B^{r-m} + H(m+1, r)$。更新 $O(\log N)$、クエリ $O(\log N)$。

2Z-algorithm
$Z[i]$ = $s[i:]$ と $s$ の最長共通プレフィックス長。$O(N)$ で計算。パターン $t$ と検索対象 $s$ を t + '$' + s と結合し、$Z[i] \geq |t|$ となる最初の $i > |t|$ を探す。

3ハッシュ衝突への対策
本解答では単一ハッシュを使用。より安全には2つの独立したハッシュ（ダブルハッシュ）を使う。Mersenne素数 $2^{61} - 1$ は衝突確率が非常に低い。

よくあるミス

ミス	原因	正しい書き方
Z-algorithm で `'$'` 番兵を入れない	`t` と `s` の境界をまたいでマッチする	必ず番兵文字を挟む
セグメント木の結合順序を逆にする	`H(l,r) = H(l,m) * B^(r-m) + H(m+1,r)`	左側に大きい冪を掛ける
1-indexed と 0-indexed の混在	クエリが1-indexed、内部処理が0-indexed	入力時に変換する
Z[0] を使い忘れる	`z[0] = n`（文字列全体）	Z-algorithm の初期値を正しく設定

次のステップ

発展問題: SA + LCP による文字列照合（Suffix Array で全パターンを $O(\log N)$ で検索）
さらに難しい: Suffix Automaton で複数パターンの同時検索（Aho-Corasick の強化版）

自己評価

完全理解おおむね理解要復習

Day 022-Q4 — 多項式ハッシュと文字列の高速照合（Rabin-Karp + Z-algorithm）

問題