概要

基準パターン \(P\) の指定区間を反転した変形パターンが、指定サンプル文字列中に何回出現するかを各クエリで求める問題です。ローリングハッシュを用いて、前処理で各サンプルの部分文字列ハッシュを辞書に格納し、クエリごとに変形パターンのハッシュを \(O(1)\) で計算して出現回数を求めます。

考察

素朴なアプローチの問題点

各クエリごとに変形パターン \(P'\) を愚直に構築し、サンプル文字列中を線形探索すると、1クエリあたり \(O(|S_i| \cdot |P|)\) かかり、\(Q\) 個のクエリで最大 \(O(Q \cdot |S_i| \cdot |P|) \approx 10^{16}\) となりTLEします。

重要な気づき

1. サンプル側の情報は固定: 各サンプルにおいて「長さ \(|P|\) の部分文字列」は高々 \(|S_i| - |P| + 1\) 個しかないので、それらすべてのハッシュ値を前計算できます。

2. 変形パターンのハッシュは \(O(1)\) で計算可能: \(P' = P[0..l\text{-}2] + \text{reverse}(P[l\text{-}1..r\text{-}1]) + P[r..|P|\text{-}1]\) という3パーツからなるので、\(P\) と反転 \(P\) の接頭辞ハッシュを前計算しておけば、各パーツのハッシュを \(O(1)\) で取得し合成できます。

3. 反転部分のハッシュ: \(P\) を反転した文字列を \(P_{\text{rev}}\) とすると、\(\text{reverse}(P[l\text{-}1..r\text{-}1])\) は \(P_{\text{rev}}[|P|\text{-}r..|P|\text{-}l]\) に対応します。

アルゴリズム

前処理

1. べき乗配列の計算: \(\text{pow}[i] = \text{BASE}^i \mod \text{MOD}\) を \(|P|\) まで計算。
2. 各サンプルのハッシュ辞書: サンプル \(S_i\) の接頭辞ハッシュを計算し、長さ \(|P|\) の全部分文字列のハッシュ値をキーとして出現回数を辞書に格納。
3. パターンの接頭辞ハッシュ: \(P\) と \(P_{\text{rev}}\)（\(P\)の反転）の接頭辞ハッシュ配列を計算。

クエリ処理

クエリ \((i, l, r)\) に対し、変形パターン \(P'\) のハッシュを以下で計算：

\[h(P') = h(\text{left}) \cdot \text{BASE}^{|P|-(l-1)} + h(\text{mid}) \cdot \text{BASE}^{|P|-r} + h(\text{right})\]

• \(h(\text{left}) = \) \(P\) の接頭辞ハッシュから \(P[0..l\text{-}2]\) のハッシュ
• \(h(\text{mid}) = \) \(P_{\text{rev}}\) の接頭辞ハッシュから \(P_{\text{rev}}[|P|\text{-}r..|P|\text{-}l]\) のハッシュ
• \(h(\text{right}) = \) \(P\) の接頭辞ハッシュから \(P[r..|P|\text{-}1]\) のハッシュ

計算したハッシュ値をキーとして、サンプル \(S_i\) の辞書から出現回数を取得します。

ハッシュ衝突対策

2つの異なるMOD（\(2^{61}-1\) と \(2^{31}-1\)）を使ったダブルハッシュで衝突確率を極限まで下げます。

計算量

• 時間計算量: \(O\left(\sum_{i=1}^{N}|S_i| + |P| + Q\right)\)
  • 前処理: サンプルのハッシュ計算に \(O(\sum |S_i|)\)、パターンの接頭辞ハッシュに \(O(|P|)\)
  • 各クエリ: \(O(1)\)（ハッシュ計算＋辞書参照）
• 空間計算量: \(O\left(\sum_{i=1}^{N}|S_i| + |P|\right)\)

実装のポイント

• MODの選択: \(2^{61}-1\) はメルセンヌ素数で、mod演算が高速かつ衝突が起きにくい。

• 反転部分のインデックス変換: \(P[l\text{-}1..r\text{-}1]\) を反転したものは、\(P_{\text{rev}}\) 上で位置 \(|P|-r\) から \(|P|-l\) に対応する点に注意（0-indexed）。

• ハッシュの合成: 3パーツを連結した文字列のハッシュは、各パーツのハッシュに適切なべき乗を掛けて足し合わせることで得られます。

• 負のmod対策: 引き算で負になりうるため、Python では自動的に正しい剰余が得られますが、他の言語では注意が必要です。

  ソースコード

import sys
from functools import lru_cache

def solve():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    
    N, Q = int(tokens[idx]), int(tokens[idx+1])
    idx += 2
    
    P = tokens[idx]
    idx += 1
    
    S = []
    for i in range(N):
        S.append(tokens[idx])
        idx += 1
    
    lenP = len(P)
    
    # Precompute rolling hashes for each sample string
    # We'll use double hashing to avoid collisions
    
    MOD1 = (1 << 61) - 1
    MOD2 = (1 << 31) - 1
    BASE1 = 131
    BASE2 = 137
    
    # Map characters to numbers
    char_map = {'H': 1, 'M': 2, 'L': 3}
    
    # For each sample, precompute hash of every substring of length lenP
    # Store in a dict: sample_index -> set/dict of hashes -> count
    
    # Precompute power arrays
    pow1 = [1] * (lenP + 1)
    pow2 = [1] * (lenP + 1)
    for i in range(1, lenP + 1):
        pow1[i] = (pow1[i-1] * BASE1) % MOD1
        pow2[i] = (pow2[i-1] * BASE2) % MOD2
    
    # For each sample, compute prefix hashes and store substring hashes
    sample_hash_counts = []
    for si in range(N):
        s = S[si]
        ls = len(s)
        hash_count = {}
        if ls >= lenP:
            # Compute prefix hashes
            ph1 = [0] * (ls + 1)
            ph2 = [0] * (ls + 1)
            for k in range(ls):
                c = char_map[s[k]]
                ph1[k+1] = (ph1[k] * BASE1 + c) % MOD1
                ph2[k+1] = (ph2[k] * BASE2 + c) % MOD2
            
            for a in range(ls - lenP + 1):
                h1 = (ph1[a + lenP] - ph1[a] * pow1[lenP]) % MOD1
                h2 = (ph2[a + lenP] - ph2[a] * pow2[lenP]) % MOD2
                key = (h1, h2)
                hash_count[key] = hash_count.get(key, 0) + 1
        
        sample_hash_counts.append(hash_count)
    
    # For pattern P, precompute prefix and suffix hashes
    P_vals = [char_map[c] for c in P]
    
    # prefix_hash1[k] = hash of P[0..k-1]
    P_prefix1 = [0] * (lenP + 1)
    P_prefix2 = [0] * (lenP + 1)
    for k in range(lenP):
        P_prefix1[k+1] = (P_prefix1[k] * BASE1 + P_vals[k]) % MOD1
        P_prefix2[k+1] = (P_prefix2[k] * BASE2 + P_vals[k]) % MOD2
    
    # suffix hash: hash of P[k..lenP-1] read forwards
    # We need hash of reversed segment P[l-1..r-1]
    # Reversed segment: P[r-1], P[r-2], ..., P[l-1]
    
    # Precompute prefix hashes of reversed P
    P_rev = P_vals[::-1]
    P_rev_prefix1 = [0] * (lenP + 1)
    P_rev_prefix2 = [0] * (lenP + 1)
    for k in range(lenP):
        P_rev_prefix1[k+1] = (P_rev_prefix1[k] * BASE1 + P_rev[k]) % MOD1
        P_rev_prefix2[k+1] = (P_rev_prefix2[k] * BASE2 + P_rev[k]) % MOD2
    
    # For query (i, l, r): P' = P[0..l-2] + reverse(P[l-1..r-1]) + P[r..lenP-1]
    # Hash of P' = hash(P[0..l-2]) * BASE^(lenP-(l-1)) + hash(reverse(P[l-1..r-1])) * BASE^(lenP-r) + hash(P[r..lenP-1])
    
    # hash(P[0..l-2]) = P_prefix[l-1]
    # hash(P[r..lenP-1]) = P_prefix[lenP] - P_prefix[r] * pow[lenP-r]
    # reverse(P[l-1..r-1]) in reversed P is at index (lenP-r) to (lenP-l)
    # hash of that = P_rev_prefix[lenP-l+1] - P_rev_prefix[lenP-r] * pow[r-l+1]
    
    out = []
    for _ in range(Q):
        ij = int(tokens[idx]) - 1
        lj = int(tokens[idx+1])
        rj = int(tokens[idx+2])
        idx += 3
        
        seg_len = rj - lj + 1
        after_len = lenP - rj
        
        # Hash1
        h1_left = P_prefix1[lj - 1]
        rev_start = lenP - rj
        rev_end = lenP - lj + 1
        h1_mid = (P_rev_prefix1[rev_end] - P_rev_prefix1[rev_start] * pow1[seg_len]) % MOD1
        h1_right = (P_prefix1[lenP] - P_prefix1[rj] * pow1[after_len]) % MOD1
        
        h1 = (h1_left * pow1[seg_len + after_len] + h1_mid * pow1[after_len] + h1_right) % MOD1
        
        # Hash2
        h2_left = P_prefix2[lj - 1]
        h2_mid = (P_rev_prefix2[rev_end] - P_rev_prefix2[rev_start] * pow2[seg_len]) % MOD2
        h2_right = (P_prefix2[lenP] - P_prefix2[rj] * pow2[after_len]) % MOD2
        
        h2 = (h2_left * pow2[seg_len + after_len] + h2_mid * pow2[after_len] + h2_right) % MOD2
        
        key = (h1 % MOD1, h2 % MOD2)
        out.append(str(sample_hash_counts[ij].get(key, 0)))
    
    sys.stdout.write('\n'.join(out) + '\n')

solve()

---

この解説は claude4.6opus-thinking によって生成されました。