概要

長さ \(N\) の列 \(A\) の中に、長さ \(M\) の列 \(B\) と完全一致する連続部分列があるかを探す問題です。
制約が大きいため、文字列検索で有名な KMP 法 を使って \(O(N+M)\) で判定します。

考察

この問題は「配列版の部分文字列検索」です。
素朴に全開始位置 \(i\)（最大 \(N-M+1\) 個）について、毎回 \(M\) 個比較すると、計算量は

[ O((N-M+1)\times M) \approx O(NM) ]

になります。
最大で \(N,M \le 5\times 10^5\) なので、最悪 \(2.5\times 10^{11}\) 比較となり、到底間に合いません（TLE）。

そこで、比較に失敗したときの情報を再利用できる KMP 法 を使います。
KMP のポイントは次の 2 段階です。

1. パターン \(B\) について、prefix function（失敗関数）\(\pi\) を作る
   
   • \(\pi[i]\) は「\(B[0..i]\) の接頭辞と接尾辞が一致する最大長」
2. \(A\) を左から 1 回走査し、失敗時に \(\pi\) を使って比較位置をジャンプする
   
   • これにより同じ要素を何度も無駄に比較しない

これで全体を線形時間にできます。

アルゴリズム

1. 入力を受け取る。
2. パターン配列 \(B\) から \(\pi\) 配列を構築する。
   • j を現在一致している長さとして持ち、
   • 不一致なら j = pi[j-1] で戻る処理を繰り返す。
3. 配列 \(A\) を左から走査して KMP 検索を行う。
   • 同様に不一致時は j = pi[j-1] で戻る。
   • 一致したら j += 1。
   • j == M になったらマッチ完成。
4. マッチ終了位置が i（0-index）なので、開始位置は i-M+1（0-index）。
   問題は 1-index で答えるので i-M+2 を出力して終了。
5. 最後まで見つからなければ -1。

計算量

• 時間計算量: \(O(N+M)\)
• 空間計算量: \(O(M)\)

実装のポイント

• KMP は「不一致時に while j > 0 and ... で戻す」部分が重要です。

• 見つかった位置の 1-index 変換に注意：

  • 0-index 開始位置 i-M+1
  • 1-index 開始位置 i-M+2

• この実装は最初に見つかった時点で return するので、最小の \(i\) を正しく出力できます。

  ソースコード

import sys


def main():
    input = sys.stdin.readline

    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    # KMP prefix function for pattern B
    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

    # KMP search in A
    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
            if j == M:
                # match ends at i (0-indexed), start is i-M+1
                print(i - M + 2)  # convert to 1-indexed
                return

    print(-1)


if __name__ == "__main__":
    main()

---

この解説は gpt-5.3-codex によって生成されました。