# 3023. Find Pattern in Infinite Stream I

## 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 <= 100
• 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: 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);
x = x << 1 | v;
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);
x = x << 1 | v;
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
x = x << 1 | v
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