概要

数列 \(A\)（本棚）の中から、数列 \(B\)（ショーウィンドウ）と完全に一致する連続した部分を探し、その開始位置を求める問題です。これは「文字列検索」のアルゴリズムを数値の列に適用することで効率的に解くことができます。

考察

素朴な方法（愚直な検索）

まず思いつくのは、本棚の各位置 \(i\) を起点として、そこから \(M\) 冊分が \(B\) と一致するかを一つずつ確認する方法です。 しかし、この方法では最悪の場合 \(O(N \times M)\) の計算量がかかります。本問題の制約は \(N, M \le 5 \times 10^5\) であるため、最大で \(2.5 \times 10^{11}\) 回程度の比較が必要になり、実行時間制限（通常 2 秒程度）を大幅に超えてしまいます。

効率的な解決策

この問題は、文字列検索アルゴリズムとして有名な KMP法 (Knuth-Morris-Pratt Algorithm) を用いることで、\(O(N + M)\) という非常に高速な時間計算量で解くことができます。

KMP法の特徴は、「不一致が起こった際、それまでに一致したという情報を活用して、比較の開始位置を無駄なくスキップする」点にあります。これにより、本棚の各要素を何度も見直す必要がなくなります。

アルゴリズム

KMP法の手順

1. 接頭辞関数（失敗関数）の構築: パターン \(B\) 自体の中に、どの程度の「繰り返しの構造」があるかを事前に計算します。具体的には、各位置 \(i\) に対して「\(B[0 \dots i]\) の接頭辞（先頭部分）と接尾辞（末尾部分）が一致する最大長」を求め、配列 pi に格納します。
2. 検索処理: 本棚 \(A\) を左から順に見ていき、パターン \(B\) と比較します。
   • もし \(A[i]\) と \(B[j]\) が一致すれば、次の要素へ進みます。
   • もし不一致が起きたら、pi 配列を参照して「次に比較すべき \(B\) の位置」までジャンプします。これにより、\(A\) のポインタを戻すことなく検索を続行できます。
3. 一致の判定: \(B\) のすべての要素（\(M\) 個）が連続して一致した瞬間、その開始位置（1-indexed なので i - M + 2）を出力して終了します。

計算量

• 時間計算量: \(O(N + M)\)
  • 事前準備に \(O(M)\)、検索処理に \(O(N)\) かかります。\(N, M = 5 \times 10^5\) の場合でも、数百万回の操作で済むため、制限時間内に十分間に合います。
• 空間計算量: \(O(N + M)\)
  • 数列 \(A, B\) および pi 配列を保持するためのメモリが必要です。

実装のポイント

• 高速な入出力: \(N, M\) が大きいため、Python の標準的な input() を繰り返すと入力だけで時間がかかる場合があります。sys.stdin.read().split() を使って一括で読み込むのが効率的です。

• 数値の扱い: 本の番号は最大 \(10^9\) と大きいですが、この問題では「値が一致するかどうか」のみが重要です。そのため、int() 型に変換せず文字列のままリストに格納して比較することで、変換コストを抑えて高速化しています。

• 1-indexed への変換: プログラミング言語の配列は通常 0 から始まりますが、問題の要求は 1 から始まるインデックス（1-indexed）であるため、出力時に調整が必要です。

  ソースコード

import sys

def solve():
    # 高速な入力を実現するために、sys.stdin.read().split() を使用してすべての入力を一度に読み込みます。
    # これにより、大量の整数（最大 10^6 個）を効率的に処理できます。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 高橋君の本棚の本の数, M: ショーウィンドウの本の数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # ショーウィンドウの並びが本棚より長い場合は一致する区間が存在しません。
    if M > N:
        print("-1")
        return
        
    # A: 本棚の番号のリスト, B: ショーウィンドウの番号のリスト
    # Pythonでは文字列のまま比較する方が、整数への変換（int()）のオーバーヘッドを避けられるため高速です。
    A = input_data[2:2+N]
    B = input_data[2+N:2+N+M]
    
    # メモリを節約するために、元の巨大なリストを削除します。
    del input_data
    
    # KMP法 (Knuth-Morris-Pratt Algorithm) を使用して、計算量 O(N + M) で一致する区間を探します。
    
    # 1. パターン B に対する接頭辞関数（失敗関数）の構築
    # pi[i] は、B[0...i] の接頭辞かつ接尾辞である最長の真の部分文字列の長さを保持します。
    pi = [0] * M
    j = 0
    for i in range(1, M):
        while j > 0 and B[i] != B[j]:
            j = pi[j-1]
        if B[i] == B[j]:
            j += 1
        pi[i] = j

    # 2. 本棚のリスト A の中からパターン B を検索
    j = 0
    for i in range(N):
        while j > 0 and A[i] != B[j]:
            j = pi[j-1]
        if A[i] == B[j]:
            j += 1
        
        # パターン B と完全に一致する区間が見つかった場合
        if j == M:
            # 1-indexed での開始位置 i - M + 2 を出力して終了します。
            # (i は現在の A のインデックス、M はパターンの長さ)
            print(i - M + 2)
            return

    # 一致する区間が見つからなかった場合
    print("-1")

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。