Overview

This is a problem of finding whether a contiguous subsequence that exactly matches a sequence \(B\) of length \(M\) exists within a sequence \(A\) of length \(N\).
Since the constraints are large, we use the well-known KMP algorithm for string searching to determine the answer in \(O(N+M)\).

Analysis

This problem is essentially “substring search for arrays.”
If we naively check all starting positions \(i\) (up to \(N-M+1\)) and compare \(M\) elements each time, the computational complexity is

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

Since \(N,M \le 5\times 10^5\) at maximum, the worst case would be \(2.5\times 10^{11}\) comparisons, which is far too slow (TLE).

Therefore, we use the KMP algorithm, which reuses information from failed comparisons.
The key points of KMP consist of the following two stages:

1. Build the prefix function (failure function) \(\pi\) for the pattern \(B\)
   
   • \(\pi[i]\) is “the maximum length where the prefix and suffix of \(B[0..i]\) match”
2. Scan \(A\) from left to right once, and use \(\pi\) to jump the comparison position upon failure
   
   • This avoids redundantly comparing the same elements multiple times

This allows the entire process to run in linear time.

Algorithm

1. Read the input.
2. Build the \(\pi\) array from the pattern array \(B\).
   • Maintain j as the current matched length.
   • On mismatch, repeatedly fall back with j = pi[j-1].
3. Scan array \(A\) from left to right and perform KMP search.
   • Similarly, on mismatch, fall back with j = pi[j-1].
   • On match, j += 1.
   • When j == M, a full match is found.
4. Since the match ending position is i (0-indexed), the starting position is i-M+1 (0-indexed).
   Since the problem requires a 1-indexed answer, output i-M+2 and terminate.
5. If no match is found after scanning the entire array, output -1.

Complexity

• Time complexity: \(O(N+M)\)
• Space complexity: \(O(M)\)

Implementation Notes

• The critical part of KMP is the while j > 0 and ... fallback on mismatch.

• Be careful with the 1-index conversion of the found position:

  • 0-indexed starting position: i-M+1
  • 1-indexed starting position: i-M+2

• This implementation returns as soon as the first match is found, so it correctly outputs the smallest \(i\).

  Source Code

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

---

This editorial was generated by gpt-5.3-codex.