Skip to content

3037. Find Pattern in Infinite Stream II πŸ”’

Description

You are given a binary array pattern and an object stream of class InfiniteStream representing a 0-indexed infinite stream of bits.

The class InfiniteStream contains the following function:

  • int next(): Reads a single bit (which is either 0 or 1) from the stream and returns it.

Return the first starting index where the pattern matches the bits read from the stream. For example, if the pattern is [1, 0], the first match is the highlighted part in the stream [0, 1, 0, 1, ...].

 

Example 1:

Input: stream = [1,1,1,0,1,1,1,...], pattern = [0,1]
Output: 3
Explanation: The first occurrence of the pattern [0,1] is highlighted in the stream [1,1,1,0,1,...], which starts at index 3.

Example 2:

Input: stream = [0,0,0,0,...], pattern = [0]
Output: 0
Explanation: The first occurrence of the pattern [0] is highlighted in the stream [0,...], which starts at index 0.

Example 3:

Input: stream = [1,0,1,1,0,1,1,0,1,...], pattern = [1,1,0,1]
Output: 2
Explanation: The first occurrence of the pattern [1,1,0,1] is highlighted in the stream [1,0,1,1,0,1,...], which starts at index 2.

 

Constraints:

  • 1 <= pattern.length <= 104
  • pattern consists only of 0 and 1.
  • stream consists only of 0 and 1.
  • The input is generated such that the pattern's start index exists in the first 105 bits of the stream.

Solutions

Solution 1

Thinking

The pattern may be as long as \(10^4\), so packing it into two \(64\)-bit words as in part I no longer works. The stream is still read-only.

This is ordinary streaming pattern matching: KMP’s failure function depends only on the pattern, so each bit advances the state without rewinding the stream.

We build the prefix function of \(\textit{pattern}\) and keep the current match length; when it reaches the pattern length we return the start index.

1


1


1


1

Comments