概要

この問題は、数列 \(A\) の中に数列 \(B\) と完全に一致する連続部分列があるかを調べ、その最初の位置を求める問題です。
\(N, M\) が大きいため、各位置から愚直に比較するのではなく、KMP 法を使って \(O(N+M)\) で解きます。

考察

この問題は、文字列ではなく整数列に対する部分一致検索です。

つまり、

• 本棚の並び \(A_1, A_2, \dots, A_N\) を「本文」
• ショーウィンドウの並び \(B_1, B_2, \dots, B_M\) を「パターン」

とみなして、\(B\) が \(A\) のどこかに現れるかを探せばよいです。

素朴な方法

各開始位置 \(i\) について、

• \(A_i\) と \(B_1\)
• \(A_{i+1}\) と \(B_2\)
• …
• \(A_{i+M-1}\) と \(B_M\)

を順に比較する方法がまず思いつきます。

しかしこの方法だと、開始位置は最大で \(N-M+1\) 個あり、各位置で最大 \(M\) 回比較するので、計算量は

\(O((N-M+1)M) \approx O(NM)\)

になります。

制約は \(N, M \le 5 \times 10^5\) なので、最悪では非常に大きくなり、到底間に合いません。

---

重要な気づき

途中まで一致していたのに不一致になったとき、最初から比較し直すのは無駄です。

たとえば、パターン \(B = [1, 2, 1, 2, 3]\) を考えます。
ここで先頭から \([1,2,1,2]\) まで一致していたとして、次で不一致になったとします。

このとき、すでに一致していた部分の末尾 \([1,2]\) は、パターンの先頭 \([1,2]\) と同じです。
つまり、パターンをずらしたあとも、一部はすでに一致していることが分かるので、その分を再利用できます。

この「どこまで一致情報を使い回せるか」を管理するのが KMP 法です。

---

KMP 法を使う理由

KMP 法では、パターン \(B\) についてあらかじめ

• 「ここまで一致していて不一致になったら、次はどこから比較すればよいか」

を表す配列を作っておきます。
これにより、本文 \(A\) を左から一度なめるだけで検索できます。

文字列検索として有名な手法ですが、この問題では比較しているのは整数同士の「等しいかどうか」だけなので、そのまま整数列にも使えます。

アルゴリズム

1. prefix function（失敗関数）を作る

パターン \(B\) に対して、配列 pi を作ります。

pi[i] の意味は、

• \(B[0..i]\) の中で
• 接頭辞でもあり接尾辞でもあるもののうち
• 最長の長さ

です。
ただし、接頭辞と接尾辞は文字列全体そのものではなく、真の接頭辞・真の接尾辞です。

例

\(B = [1, 2, 1, 2, 3]\) のとき、

• pi[0] = 0
• pi[1] = 0
• pi[2] = 1 （[1] が共通）
• pi[3] = 2 （[1,2] が共通）
• pi[4] = 0

となります。

この pi を使うと、不一致が起きたときに「次にどこまで一致しているものとして扱えるか」がすぐ分かります。

---

2. 数列 \(A\) の中を走査する

変数 j を

• 「今、パターン \(B\) の先頭から何個一致しているか」

として持ちます。

\(A\) を左から順に見ていき、\(A[i]\) と \(B[j]\) を比較します。

• 一致すれば j += 1
• 不一致なら、pi を使って j を戻し、再び比較します

これにより、すでに分かっている一致情報を無駄にせずに進めます。

j == M になったら、パターン全体が一致したことになります。
このとき一致区間の終端は \(i\)（0-indexed）なので、開始位置は

\( i - M + 1 \)

です。
問題は 1-indexed で答えるので、出力は

\( i - M + 2 \)

になります。

---

3. 最初に見つかった位置を出力する

左から順に検索しているので、最初に j == M になった位置がそのまま最小の \(i\) です。
見つかったら即座に出力して終了します。
最後まで見つからなければ -1 を出力します。

計算量

• 時間計算量: \(O(N+M)\)
• 空間計算量: \(O(M)\) （pi 配列。入力配列も含めた実装全体では \(O(N+M)\)）

実装のポイント

• KMP 法は文字列だけでなく、等値比較できる列ならそのまま使えます。この問題では整数列なので問題ありません。
• while j > 0 and ... で不一致時に j = pi[j-1] と戻すのが KMP の核心です。
• 一致したときに j == M になったら、答えは i - M + 2 です。
  これは
  • i - M + 1 が 0-indexed の開始位置
  • さらに 1-indexed に直して +1

した結果です。 - この実装では sys.stdin.buffer.read() を使って高速に入力を読んでおり、大きな入力でも対応できます。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N, M = data[0], data[1]
    A = data[2:2 + N]
    B = data[2 + N:2 + N + M]

    # 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

    # Search B 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:
                print(i - M + 2)  # 1-based index
                return

    print(-1)

if __name__ == "__main__":
    main()

---

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