Overview

This problem asks you to determine whether a contiguous subsequence that exactly matches a sequence \(B\) of length \(M\) exists within a sequence \(A\) of length \(N\), and if so, find the minimum starting position. It is essentially the sequence version of “substring search.”

Analysis

Naive Approach and Its Issues

The simplest method is to compare \(A_i, A_{i+1}, \dots, A_{i+M-1}\) with \(B_1, B_2, \dots, B_M\) element by element for every starting position \(i\) (\(1 \le i \le N - M + 1\)) in \(A\).

• There are at most \(N - M + 1\) candidate starting positions
• Each candidate requires at most \(M\) comparisons

Thus, the worst-case complexity is \(O(N \times M)\). When both \(N\) and \(M\) are \(5 \times 10^5\), this requires up to \(2.5 \times 10^{11}\) operations, resulting in TLE (Time Limit Exceeded).

Optimization Idea: Rolling Hash

To address this, we use the Rabin-Karp algorithm (rolling hash). The basic idea is as follows:

1. Compute the hash value of the entire sequence \(B\)
2. Compute the hash value of each contiguous interval of length \(M\) in \(A\), updating it in \(O(1)\) as we slide the window
3. Only when hash values match, verify by comparing elements one by one

If the hashes don’t match, we can immediately skip that position, so most positions are rejected in \(O(1)\), making the overall algorithm fast.

Algorithm

How Rolling Hash Works

For a sequence \(X_1, X_2, \dots, X_M\), we define the hash value using a base \(b\) and a modulus \(p\) as follows:

\[H(X) = (X_1 \cdot b^{M-1} + X_2 \cdot b^{M-2} + \cdots + X_M \cdot b^0) \mod p\]

Sliding update: Updating the hash from \(A_i, \dots, A_{i+M-1}\) to \(A_{i+1}, \dots, A_{i+M}\) is done in \(O(1)\) with the following formula:

\[H_{\text{new}} = (H_{\text{old}} \times b + A_{i+M} - A_i \times b^M) \mod p\]

Countermeasures Against Hash Collisions

With a single hash, different sequences may have the same hash value (collision). This code uses two independent hashes (with different bases and moduli) to make the collision probability extremely small:

• Hash 1: \(b = 131\), \(p = 2^{61} - 1\) (Mersenne prime)
• Hash 2: \(b = 137\), \(p = 2^{31} - 1\) (Mersenne prime)

Only when both hashes match do we perform the actual element-by-element comparison for final verification.

Processing Flow

1. Compute the hash values (2 types) of \(B\)
2. Compute the hash values of the first interval of length \(M\) in \(A\) and compare with \(B\)
3. Shift the starting position one to the right at a time, updating the hash in \(O(1)\) and checking for a match
4. If the hashes match, directly compare elements; if they truly match, output that position
5. If no match is found by the end, output \(-1\)

Concrete Example

For \(A = [3, 1, 4, 1, 5]\), \(B = [4, 1, 5]\) (\(N=5, M=3\)):

Starting position \(i\)	Interval	Hash match?	Result
1	\([3,1,4]\)	No	Skip
2	\([1,4,1]\)	No	Skip
3	\([4,1,5]\)	Yes → Element comparison also matches	Answer: 3

Complexity

• Time complexity: \(O(N + M)\) (in the average case. Since hash collisions almost never occur, the cost of element comparison is negligible. The worst case is \(O(NM)\), but this practically never happens)
• Space complexity: \(O(N + M)\) (for storing the input sequences)

Implementation Notes

• Using Mersenne primes as moduli: \(2^{61}-1\) and \(2^{31}-1\) are primes with good properties for modular arithmetic, making collisions less likely

• Double hashing: By using two independent hashes, the collision probability is reduced to approximately \(O(1/p_1 \cdot 1/p_2)\)

• Actual comparison on hash match: Since correctness is not guaranteed by hashes alone, all elements are directly compared when a match occurs (as a safety measure)

• Fast input reading: sys.stdin.buffer.read() is used to mitigate the input bottleneck in Python

• Precomputation of \(b^M \mod p\): The value \(b^M\), which is used in every rolling update, is precomputed using pow(BASE, M, MOD)

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = input_data[idx:idx+N]; idx += N
    B = input_data[idx:idx+M]; idx += M

    if M > N:
        print(-1)
        return

    # Rabin-Karp style matching with rolling hash
    # Convert to integer arrays
    # Use two hashes to reduce collision probability
    
    MOD1 = (1 << 61) - 1
    BASE1 = 131

    MOD2 = (1 << 31) - 1
    BASE2 = 137

    def mod_mul(a, b, mod):
        return a * b % mod

    # Compute hash of B
    hash_b1 = 0
    hash_b2 = 0
    for j in range(M):
        v = int(B[j])
        hash_b1 = (hash_b1 * BASE1 + v) % MOD1
        hash_b2 = (hash_b2 * BASE2 + v) % MOD2

    # Compute BASE1^M mod MOD1 and BASE2^M mod MOD2
    pow1 = pow(BASE1, M, MOD1)
    pow2 = pow(BASE2, M, MOD2)

    # Compute hash of A[0..M-1]
    hash_a1 = 0
    hash_a2 = 0
    A_int = [int(x) for x in A]
    for j in range(M):
        hash_a1 = (hash_a1 * BASE1 + A_int[j]) % MOD1
        hash_a2 = (hash_a2 * BASE2 + A_int[j]) % MOD2

    if hash_a1 == hash_b1 and hash_a2 == hash_b2:
        # Verify
        match = True
        for j in range(M):
            if A_int[j] != int(B[j]):
                match = False
                break
        if match:
            print(1)
            return

    B_int = [int(x) for x in B]

    for i in range(1, N - M + 1):
        hash_a1 = (hash_a1 * BASE1 + A_int[i + M - 1] - A_int[i - 1] * pow1) % MOD1
        hash_a2 = (hash_a2 * BASE2 + A_int[i + M - 1] - A_int[i - 1] * pow2) % MOD2
        if hash_a1 == hash_b1 and hash_a2 == hash_b2:
            match = True
            for j in range(M):
                if A_int[i + j] != B_int[j]:
                    match = False
                    break
            if match:
                print(i + 1)
                return

    print(-1)

solve()

---

This editorial was generated by claude4.6opus-thinking.