Overview

This is a problem where you need to find a contiguous subsequence within sequence \(A\) (bookshelf) that exactly matches sequence \(B\) (showwindow), and determine its starting position. This can be solved efficiently by applying a “string search” algorithm to sequences of numbers.

Analysis

Naive Method (Brute Force Search)

The first approach that comes to mind is to start from each position \(i\) in the bookshelf and check one by one whether the \(M\) elements starting from there match \(B\). However, this method has a worst-case time complexity of \(O(N \times M)\). Given the constraints of this problem where \(N, M \le 5 \times 10^5\), this would require up to approximately \(2.5 \times 10^{11}\) comparisons, far exceeding the time limit (typically around 2 seconds).

Efficient Solution

This problem can be solved with a very fast time complexity of \(O(N + M)\) by using the well-known string search algorithm KMP (Knuth-Morris-Pratt Algorithm).

The key feature of the KMP algorithm is that “when a mismatch occurs, it utilizes the information about what has already matched to efficiently skip ahead in the comparison starting position.” This eliminates the need to re-examine each element of the bookshelf multiple times.

Algorithm

KMP Algorithm Steps

1. Building the Prefix Function (Failure Function): We precompute how much “repetitive structure” exists within pattern \(B\) itself. Specifically, for each position \(i\), we find the maximum length where a prefix (beginning part) and suffix (ending part) of \(B[0 \dots i]\) are equal, and store this in the array pi.
2. Search Process: We scan through bookshelf \(A\) from left to right, comparing with pattern \(B\).
   • If \(A[i]\) and \(B[j]\) match, we advance to the next element.
   • If a mismatch occurs, we refer to the pi array to jump to “the next position in \(B\) that should be compared.” This allows the search to continue without moving the pointer in \(A\) backward.
3. Match Detection: The moment all elements of \(B\) (\(M\) elements) match consecutively, we output the starting position (since it’s 1-indexed: i - M + 2) and terminate.

Complexity

• Time Complexity: \(O(N + M)\)
  • The preprocessing takes \(O(M)\) and the search process takes \(O(N)\). Even when \(N, M = 5 \times 10^5\), it only requires a few million operations, which is well within the time limit.
• Space Complexity: \(O(N + M)\)
  • Memory is needed to store sequences \(A\), \(B\), and the pi array.

Implementation Notes

• Fast I/O: Since \(N, M\) can be large, repeatedly using Python’s standard input() may cause the input alone to be too slow. It is efficient to read everything at once using sys.stdin.read().split().

• Handling Numbers: Book numbers can be as large as \(10^9\), but in this problem only “whether values match or not” matters. Therefore, instead of converting to int() type, we store them as strings in a list and compare them that way, reducing conversion costs and improving speed.

• Conversion to 1-indexed: Arrays in programming languages typically start from 0, but the problem requires 1-based indexing (1-indexed), so an adjustment is needed when outputting.

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.