Welcome to Subscribe On Youtube
3023. Find Pattern in Infinite Stream I
Description
You are given a binary array pattern
and an object stream
of class InfiniteStream
representing a 0indexed infinite stream of bits.
The class InfiniteStream
contains the following function:
int next()
: Reads a single bit (which is either0
or1
) 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 <= 100
pattern
consists only of0
and1
.stream
consists only of0
and1
. The input is generated such that the pattern's start index exists in the first
10^{5}
bits of the stream.
Solutions
Solution 1: Bit Manipulation + Sliding Window
We notice that the length of the array $pattern$ does not exceed $100$, therefore, we can use two $64$bit integers $a$ and $b$ to represent the binary numbers of the left and right halves of $pattern$.
Next, we traverse the data stream, also maintaining two $64$bit integers $x$ and $y$ to represent the binary numbers of the current window of the length of $pattern$. If the current length reaches the window length, we compare whether $a$ and $x$ are equal, and whether $b$ and $y$ are equal. If they are, we return the index of the current data stream.
The time complexity is $O(n + m)$, where $n$ and $m$ are the number of elements in the data stream and $pattern$ respectively. The space complexity is $O(1)$.

/** * Definition for an infinite stream. * class InfiniteStream { * public InfiniteStream(int[] bits); * public int next(); * } */ class Solution { public int findPattern(InfiniteStream infiniteStream, int[] pattern) { long a = 0, b = 0; int m = pattern.length; int half = m >> 1; long mask1 = (1L << half)  1; long mask2 = (1L << (m  half))  1; for (int i = 0; i < half; ++i) { a = (long) pattern[i] << (half  1  i); } for (int i = half; i < m; ++i) { b = (long) pattern[i] << (m  1  i); } long x = 0, y = 0; for (int i = 1;; ++i) { int v = infiniteStream.next(); y = y << 1  v; v = (int) ((y >> (m  half)) & 1); y &= mask2; x = x << 1  v; x &= mask1; if (i >= m && a == x && b == y) { return i  m; } } } }

/** * Definition for an infinite stream. * class InfiniteStream { * public: * InfiniteStream(vector<int> bits); * int next(); * }; */ class Solution { public: int findPattern(InfiniteStream* stream, vector<int>& pattern) { long long a = 0, b = 0; int m = pattern.size(); int half = m >> 1; long long mask1 = (1LL << half)  1; long long mask2 = (1LL << (m  half))  1; for (int i = 0; i < half; ++i) { a = (long long) pattern[i] << (half  1  i); } for (int i = half; i < m; ++i) { b = (long long) pattern[i] << (m  1  i); } long x = 0, y = 0; for (int i = 1;; ++i) { int v = stream>next(); y = y << 1  v; v = (int) ((y >> (m  half)) & 1); y &= mask2; x = x << 1  v; x &= mask1; if (i >= m && a == x && b == y) { return i  m; } } } };

# Definition for an infinite stream. # class InfiniteStream: # def next(self) > int: # pass class Solution: def findPattern( self, stream: Optional["InfiniteStream"], pattern: List[int] ) > int: a = b = 0 m = len(pattern) half = m >> 1 mask1 = (1 << half)  1 mask2 = (1 << (m  half))  1 for i in range(half): a = pattern[i] << (half  1  i) for i in range(half, m): b = pattern[i] << (m  1  i) x = y = 0 for i in count(1): v = stream.next() y = y << 1  v v = y >> (m  half) & 1 y &= mask2 x = x << 1  v x &= mask1 if i >= m and a == x and b == y: return i  m

/** * Definition for an infinite stream. * type InfiniteStream interface { * Next() int * } */ func findPattern(stream InfiniteStream, pattern []int) int { a, b := 0, 0 m := len(pattern) half := m >> 1 mask1 := (1 << half)  1 mask2 := (1 << (m  half))  1 for i := 0; i < half; i++ { a = pattern[i] << (half  1  i) } for i := half; i < m; i++ { b = pattern[i] << (m  1  i) } x, y := 0, 0 for i := 1; ; i++ { v := stream.Next() y = y<<1  v v = (y >> (m  half)) & 1 y &= mask2 x = x<<1  v x &= mask1 if i >= m && a == x && b == y { return i  m } } }