概要

長さ \(N\) の数列 \(A\) の中に、長さ \(M\) の数列 \(B\) と完全に一致する連続部分列が存在するかを判定し、存在すれば最小の開始位置を求める問題です。いわゆる「部分文字列検索」の数列版です。

考察

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

最も単純な方法は、\(A\) のすべての開始位置 \(i\)（\(1 \le i \le N - M + 1\)）について、\(A_i, A_{i+1}, \dots, A_{i+M-1}\) と \(B_1, B_2, \dots, B_M\) を1要素ずつ比較することです。

• 開始位置の候補は最大 \(N - M + 1\) 個
• 各候補について最大 \(M\) 回の比較

よって最悪計算量は \(O(N \times M)\) となります。\(N, M\) がともに \(5 \times 10^5\) の場合、最大 \(2.5 \times 10^{11}\) 回の演算が必要になり、TLE（時間超過） になります。

高速化のアイデア：ローリングハッシュ

そこで Rabin-Karp 法（ローリングハッシュ） を使います。基本的なアイデアは次の通りです：

1. 数列 \(B\) 全体のハッシュ値を計算する
2. \(A\) の長さ \(M\) の連続区間のハッシュ値を、スライドさせながら \(O(1)\) で更新する
3. ハッシュ値が一致した場合のみ、実際に要素を1つずつ比較して確認する

ハッシュが一致しなければ即座にスキップできるので、ほとんどの位置を \(O(1)\) で棄却でき、全体として高速に動作します。

アルゴリズム

ローリングハッシュの仕組み

数列 \(X_1, X_2, \dots, X_M\) に対して、基数 \(b\) と法 \(p\) を用いたハッシュ値を次のように定義します：

\[H(X) = (X_1 \cdot b^{M-1} + X_2 \cdot b^{M-2} + \cdots + X_M \cdot b^0) \mod p\]

スライド更新：\(A_i, \dots, A_{i+M-1}\) のハッシュから \(A_{i+1}, \dots, A_{i+M}\) のハッシュへの更新は次の式で \(O(1)\) です：

\[H_{\text{new}} = (H_{\text{old}} \times b + A_{i+M} - A_i \times b^M) \mod p\]

ハッシュ衝突への対策

1つのハッシュだけでは異なる数列が同じハッシュ値を持つ（衝突する）可能性があります。本コードでは 2つの独立なハッシュ（異なる基数・法）を使い、衝突確率を極めて小さくしています：

• ハッシュ1：\(b = 131\), \(p = 2^{61} - 1\)（メルセンヌ素数）
• ハッシュ2：\(b = 137\), \(p = 2^{31} - 1\)（メルセンヌ素数）

両方のハッシュが一致した場合にのみ、実際の要素比較で最終確認を行います。

処理の流れ

1. \(B\) のハッシュ値（2種類）を計算
2. \(A\) の最初の長さ \(M\) の区間のハッシュ値を計算し、\(B\) と比較
3. 開始位置を1つずつ右にずらしながらハッシュを \(O(1)\) で更新し、一致判定
4. ハッシュが一致したら要素を直接比較し、本当に一致すればその位置を出力
5. 最後まで見つからなければ \(-1\) を出力

具体例

\(A = [3, 1, 4, 1, 5]\), \(B = [4, 1, 5]\)（\(N=5, M=3\)）の場合：

開始位置 \(i\)	区間	ハッシュ一致?	結果
1	\([3,1,4]\)	No	スキップ
2	\([1,4,1]\)	No	スキップ
3	\([4,1,5]\)	Yes → 要素比較も一致	答え: 3

計算量

• 時間計算量: \(O(N + M)\)（平均的な場合。ハッシュ衝突がほぼ起きないため、要素比較のコストは無視できる。最悪でも \(O(NM)\) だが実質発生しない）
• 空間計算量: \(O(N + M)\)（入力の数列を保持するため）

実装のポイント

• 法にメルセンヌ素数を使用: \(2^{61}-1\) や \(2^{31}-1\) は素数であり、剰余演算の性質が良く衝突が起きにくい

• ダブルハッシュ: 2つの独立なハッシュを使うことで、衝突確率を \(O(1/p_1 \cdot 1/p_2)\) 程度まで下げている

• ハッシュ一致時の実比較: ハッシュだけでは正しさが保証されないため、一致した場合は必ず全要素を直接比較する（安全策）

• 入力の高速読み込み: sys.stdin.buffer.read() を使い、Python での入力ボトルネックを軽減している

• \(b^M \mod p\) の事前計算: ローリング更新で毎回使う \(b^M\) を pow(BASE, M, MOD) で事前に求めておく

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = input_data[idx:idx+N]; idx += N
    B = input_data[idx:idx+M]; idx += M

    if M > N:
        print(-1)
        return

    # Rabin-Karp style matching with rolling hash
    # Convert to integer arrays
    # Use two hashes to reduce collision probability
    
    MOD1 = (1 << 61) - 1
    BASE1 = 131

    MOD2 = (1 << 31) - 1
    BASE2 = 137

    def mod_mul(a, b, mod):
        return a * b % mod

    # Compute hash of B
    hash_b1 = 0
    hash_b2 = 0
    for j in range(M):
        v = int(B[j])
        hash_b1 = (hash_b1 * BASE1 + v) % MOD1
        hash_b2 = (hash_b2 * BASE2 + v) % MOD2

    # Compute BASE1^M mod MOD1 and BASE2^M mod MOD2
    pow1 = pow(BASE1, M, MOD1)
    pow2 = pow(BASE2, M, MOD2)

    # Compute hash of A[0..M-1]
    hash_a1 = 0
    hash_a2 = 0
    A_int = [int(x) for x in A]
    for j in range(M):
        hash_a1 = (hash_a1 * BASE1 + A_int[j]) % MOD1
        hash_a2 = (hash_a2 * BASE2 + A_int[j]) % MOD2

    if hash_a1 == hash_b1 and hash_a2 == hash_b2:
        # Verify
        match = True
        for j in range(M):
            if A_int[j] != int(B[j]):
                match = False
                break
        if match:
            print(1)
            return

    B_int = [int(x) for x in B]

    for i in range(1, N - M + 1):
        hash_a1 = (hash_a1 * BASE1 + A_int[i + M - 1] - A_int[i - 1] * pow1) % MOD1
        hash_a2 = (hash_a2 * BASE2 + A_int[i + M - 1] - A_int[i - 1] * pow2) % MOD2
        if hash_a1 == hash_b1 and hash_a2 == hash_b2:
            match = True
            for j in range(M):
                if A_int[i + j] != B_int[j]:
                    match = False
                    break
            if match:
                print(i + 1)
                return

    print(-1)

solve()

---

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