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:# def next(self) -> int:# passclassSolution:deffindPattern(self,stream:Optional["InfiniteStream"],pattern:List[int])->int:a=b=0m=len(pattern)half=m>>1mask1=(1<<half)-1mask2=(1<<(m-half))-1foriinrange(half):a|=pattern[i]<<(half-1-i)foriinrange(half,m):b|=pattern[i]<<(m-1-i)x=y=0foriincount(1):v=stream.next()y=y<<1|vv=y>>(m-half)&1y&=mask2x=x<<1|vx&=mask1ifi>=manda==xandb==y:returni-m
/** * Definition for an infinite stream. * class InfiniteStream { * public InfiniteStream(int[] bits); * public int next(); * } */classSolution{publicintfindPattern(InfiniteStreaminfiniteStream,int[]pattern){longa=0,b=0;intm=pattern.length;inthalf=m>>1;longmask1=(1L<<half)-1;longmask2=(1L<<(m-half))-1;for(inti=0;i<half;++i){a|=(long)pattern[i]<<(half-1-i);}for(inti=half;i<m;++i){b|=(long)pattern[i]<<(m-1-i);}longx=0,y=0;for(inti=1;;++i){intv=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){returni-m;}}}}
/** * Definition for an infinite stream. * type InfiniteStream interface { * Next() int * } */funcfindPattern(streamInfiniteStream,pattern[]int)int{a,b:=0,0m:=len(pattern)half:=m>>1mask1:=(1<<half)-1mask2:=(1<<(m-half))-1fori:=0;i<half;i++{a|=pattern[i]<<(half-1-i)}fori:=half;i<m;i++{b|=pattern[i]<<(m-1-i)}x,y:=0,0fori:=1;;i++{v:=stream.Next()y=y<<1|vv=(y>>(m-half))&1y&=mask2x=x<<1|vx&=mask1ifi>=m&&a==x&&b==y{returni-m}}}