Overview

This problem asks whether there exists a contiguous subsequence in sequence \(A\) that exactly matches sequence \(B\), and if so, to find its first position. Since \(N, M\) can be large, instead of naively comparing from each position, we use the KMP algorithm to solve it in \(O(N+M)\).

Approach

This problem is essentially a substring matching problem on integer sequences rather than strings.

In other words,

• Treat the bookshelf arrangement \(A_1, A_2, \dots, A_N\) as the “text”
• Treat the showwindow arrangement \(B_1, B_2, \dots, B_M\) as the “pattern”

and search for whether \(B\) appears somewhere in \(A\).

Naive Method

For each starting position \(i\), the first idea is to compare:

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

in order.

However, with this method, there are up to \(N-M+1\) starting positions, and each position requires up to \(M\) comparisons, so the time complexity is

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

Given the constraints \(N, M \le 5 \times 10^5\), this can become extremely large in the worst case and is far too slow.

---

Key Insight

When a mismatch occurs after partially matching, starting the comparison over from scratch is wasteful.

For example, consider the pattern \(B = [1, 2, 1, 2, 3]\). Suppose we matched \([1,2,1,2]\) from the beginning, and then a mismatch occurred at the next position.

At this point, the tail \([1,2]\) of the already-matched portion is the same as the beginning \([1,2]\) of the pattern. This means that even after shifting the pattern, we already know that part of it matches, so we can reuse that information.

Managing “how much of the match information can be reused” is exactly what the KMP algorithm does.

---

Why Use the KMP Algorithm

In the KMP algorithm, we precompute for pattern \(B\):

• “If we’ve matched up to here and then get a mismatch, where should we resume comparison from?”

stored in an array. This allows us to search by scanning the text \(A\) from left to right just once.

While this is a well-known technique for string searching, in this problem we are only comparing integers for equality, so it can be applied directly to integer sequences.

Algorithm

1. Build the Prefix Function (Failure Function)

For pattern \(B\), we build the array pi.

The meaning of pi[i] is:

• Within \(B[0..i]\),
• the length of the longest substring that is both a prefix and a suffix,
• excluding the entire string itself (i.e., proper prefix and proper suffix).

Example

For \(B = [1, 2, 1, 2, 3]\):

• pi[0] = 0
• pi[1] = 0
• pi[2] = 1 ([1] is common)
• pi[3] = 2 ([1,2] is common)
• pi[4] = 0

Using this pi, when a mismatch occurs, we can immediately determine “how far we can assume is still matched.”

---

2. Scan Through Sequence \(A\)

We maintain a variable j representing:

• “How many elements from the beginning of pattern \(B\) currently match.”

We scan \(A\) from left to right and compare \(A[i]\) with \(B[j]\).

• If they match, j += 1
• If they don’t match, use pi to fall back j, then compare again

This way, we proceed without wasting already-known match information.

When j == M, the entire pattern has been matched. At this point, the end of the matching interval is \(i\) (0-indexed), so the starting position is

\( i - M + 1 \)

Since the problem uses 1-indexed answers, the output is

\( i - M + 2 \)

---

3. Output the First Found Position

Since we search from left to right, the first position where j == M is the smallest such \(i\). Once found, we output it immediately and terminate. If nothing is found by the end, we output -1.

Complexity

• Time complexity: \(O(N+M)\)
• Space complexity: \(O(M)\) (for the pi array; \(O(N+M)\) for the entire implementation including input arrays)

Implementation Notes

• The KMP algorithm works not only on strings but on any sequence with equality comparison. Since this problem uses integer sequences, there is no issue.
• The core of KMP is falling back with j = pi[j-1] inside while j > 0 and ... when a mismatch occurs.
• When a match is found (j == M), the answer is i - M + 2. This is because:
  • i - M + 1 is the 0-indexed starting position
  • Adding +1 to convert to 1-indexed

gives the result. - This implementation uses sys.stdin.buffer.read() for fast input reading, which handles large inputs efficiently.

Source Code

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

---

This editorial was generated by gpt-5.4-high.