Find Pattern in Infinite Binary Stream I
Given infinite stream of binary bits. The stream is represented by an InfiniteStream object with a next() function that returns the next bit. The task is to find the starting index of the first occurrence of a given binary pattern in an infinite stream of bits. For example, if the pattern is [1, 0], return the index where this pattern first appears in the stream.
Example:
Input: stream = [1,1,1,0,1,1,1,…], pattern = [0,1]
Output: 3
Explanation: The first occurrence of this pattern is found starting at index 3 in the stream.Input: stream = [0,0,0,0,…], pattern = [0]
Output: 0Input: stream = [1,0,1,1,0,1,1,0,1,…], pattern = [1,1,0,1]
Output: 2
Approach:
Use a Rolling hash (Rabin-Karp Algorithm). In this method, we maintain a hash of the current window of bits in the stream and compare it with the hash of the pattern. The hash is updated in each step by removing the leftmost bit, shifting the remaining bits to the left (equivalent to multiplying by 2), and adding the new bit.
Here’s an example with stream = [1,0,1,1,0,1,1,0,1,…] and pattern = [1,1,0,1]:
- Compute the hash of the pattern: hashp = binary(1101)
- Initialize the stream hash: hashs = binary(1011)
- For each new bit in the stream:
- Update the stream hash: hashs = (hashs – binary(1000)) * 2 + new_bit
- If hashs equals hashp, we’ve found the pattern
This approach reduces the time complexity to O(m), where m is the stream length. It avoids unnecessary comparisons by using the fact that most of the bits in the current window are the same as in the previous window. The only bits that change are the leftmost bit (which is removed) and the rightmost bit (which is added).
Steps-by-step approach:
- Takes an InfiniteStream pointer and a pattern vector as input.
- Calculates the hash for the pattern and the initial window hash.
- Compares the initial window hash with the pattern hash to check if the pattern exists at the beginning of the stream.
- If not found at the beginning, initializes variables for window management:
- current_index: Index of the first element in the current window.
- unset_mask: Mask to unset the largest bit in the window hash.
- Enters a loop to iterate over the stream:
- Unsets the largest bit from the window hash and shifts it to the left, simulating the movement of the window.
- Retrieves the next element from the stream and updates the window hash accordingly.
- Checks if the current window hash matches the pattern hash.
- If found, returns the current index.
- Otherwise, increments the index and continues searching.
- Returns -1 if the pattern is not found in the stream.
Below is the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
#include <vector>
using namespace std;
class InfiniteStream {
private:
vector<int> bits;
int index;
public:
InfiniteStream(vector<int> bits)
: bits(bits)
, index(0)
{
}
int next()
{
// Return the next bit in the stream and increment
// the index
return bits[index++];
}
};
int findPattern(InfiniteStream* stream,
vector<int>& pattern)
{
// Calculate the hash for the pattern.
long long pattern_hash = 0;
for (int i = 0; i < pattern.size(); i++) {
pattern_hash = (pattern_hash << 1)
| pattern[i]; // Efficiently shift
// and add bits
}
// Calculate the initial window hash.
long long window_hash = 0;
for (int i = 0; i < pattern.size(); i++) {
int current = stream->next();
window_hash
= (window_hash << 1)
| current; // Efficiently shift and add bits
}
// Check if the initial window matches the pattern.
if (window_hash == pattern_hash) {
return 0; // Pattern found at the beginning of the
// stream
}
// Initialize variables for window management.
int current_index = 1; // Index of the first element in
// the current window
long long unset_mask
= (1LL << (pattern.size() - 1))
- 1; // Mask to unset the largest bit
while (true) {
// Unset the largest bit from the window hash,
// representing the element leaving the window.
window_hash &= unset_mask;
window_hash
<<= 1; // Shift the window hash to the left
// Get the next element from the stream and update
// the window hash.
int current = stream->next();
if (current == 1) {
window_hash |= 1; // Set the least significant
// bit if the element is 1
}
// Check if the current window matches the pattern.
if (window_hash == pattern_hash) {
return current_index; // Pattern found at the
// current index
}
else {
current_index++; // Move the window forward
}
}
return -1; // Pattern not found
}
int main()
{
// Initialize the stream and pattern
vector<int> stream = { 1, 1, 1, 0, 1, 1, 1 };
vector<int> pattern = { 0, 1 };
// Create an InfiniteStream object
InfiniteStream* infiniteStream
= new InfiniteStream(stream);
// Find the pattern in the stream
int index = findPattern(infiniteStream, pattern);
// Print the result
if (index != -1) {
cout << "Pattern found at index " << index << endl;
}
else {
cout << "Pattern not found" << endl;
}
// Clean up
delete infiniteStream;
return 0;
}
import java.util.Arrays;
import java.util.List;
class InfiniteStream {
private final List<Integer> bits;
private int index;
public InfiniteStream(List<Integer> bits)
{
this.bits = bits;
this.index = 0;
}
public int next()
{
// Return the next bit in the stream and increment
// the index
int bit = this.bits.get(this.index);
this.index++;
return bit;
}
}
public class Main {
public static int findPattern(InfiniteStream stream,
List<Integer> pattern)
{
// Calculate the hash for the pattern.
int patternHash = 0;
for (int bit : pattern) {
// Efficiently shift and add bits
patternHash = (patternHash << 1) | bit;
}
// Calculate the initial window hash.
int windowHash = 0;
for (int i = 0; i < pattern.size(); i++) {
int current = stream.next();
// Efficiently shift and add bits
windowHash = (windowHash << 1) | current;
}
// Check if the initial window matches the pattern.
if (windowHash == patternHash) {
return 0; // Pattern found at the beginning of
// the stream
}
// Initialize variables for window management.
int currentIndex = 1; // Index of the first element
// in the current window
int unsetMask
= (1 << (pattern.size() - 1))
- 1; // Mask to unset the largest bit
while (true) {
// Unset the largest bit from the window hash,
// representing the element leaving the window.
windowHash &= unsetMask;
windowHash
<<= 1; // Shift the window hash to the left
// Get the next element from the stream and
// update the window hash.
int current = stream.next();
if (current == 1) {
windowHash
|= 1; // Set the least significant bit
// if the element is 1
}
// Check if the current window matches the
// pattern.
if (windowHash == patternHash) {
return currentIndex; // Pattern found at the
// current index
}
else {
currentIndex++; // Move the window forward
}
}
}
public static void main(String[] args)
{
// Initialize the stream and pattern
Integer[] stream = { 1, 1, 1, 0, 1, 1, 1 };
Integer[] pattern = { 0, 1 };
// Create an InfiniteStream object
InfiniteStream infiniteStream
= new InfiniteStream(Arrays.asList(stream));
// Find the pattern in the stream
int index = findPattern(infiniteStream,
Arrays.asList(pattern));
// Print the result
if (index != -1) {
System.out.println("Pattern found at index "
+ index);
}
else {
System.out.println("Pattern not found");
}
}
}
class InfiniteStream:
def __init__(self, bits):
self.bits = bits
self.index = 0
def next(self):
# Return the next bit in the stream and increment the index
bit = self.bits[self.index]
self.index += 1
return bit
def findPattern(stream, pattern):
# Calculate the hash for the pattern.
pattern_hash = 0
for bit in pattern:
# Efficiently shift and add bits
pattern_hash = (pattern_hash << 1) | bit
# Calculate the initial window hash.
window_hash = 0
for _ in range(len(pattern)):
current = stream.next()
# Efficiently shift and add bits
window_hash = (window_hash << 1) | current
# Check if the initial window matches the pattern.
if window_hash == pattern_hash:
return 0 # Pattern found at the beginning of the stream
# Initialize variables for window management.
current_index = 1 # Index of the first element in the current window
unset_mask = (1 << (len(pattern) - 1)) - 1 # Mask to unset the largest bit
while True:
# Unset the largest bit from the window hash, representing the element leaving the window.
window_hash &= unset_mask
window_hash <<= 1 # Shift the window hash to the left
# Get the next element from the stream and update the window hash.
current = stream.next()
if current == 1:
window_hash |= 1 # Set the least significant bit if the element is 1
# Check if the current window matches the pattern.
if window_hash == pattern_hash:
return current_index # Pattern found at the current index
else:
current_index += 1 # Move the window forward
return -1 # Pattern not found
def main():
# Initialize the stream and pattern
stream = [1, 1, 1, 0, 1, 1, 1]
pattern = [0, 1]
# Create an InfiniteStream object
infiniteStream = InfiniteStream(stream)
# Find the pattern in the stream
index = findPattern(infiniteStream, pattern)
# Print the result
if index != -1:
print("Pattern found at index", index)
else:
print("Pattern not found")
if __name__ == "__main__":
main()
class InfiniteStream {
constructor(bits) {
this.bits = bits;
this.index = 0;
}
next() {
const bit = this.bits[this.index];
this.index++;
return bit;
}
}
function findPattern(stream, pattern) {
// Calculate the hash for the pattern.
let patternHash = 0;
for (const bit of pattern) {
// Efficiently shift and add bits
patternHash = (patternHash << 1) | bit;
}
// Calculate the initial window hash.
let windowHash = 0;
for (let i = 0; i < pattern.length; i++) {
const current = stream.next();
// Efficiently shift and add bits
windowHash = (windowHash << 1) | current;
}
// Check if the initial window matches the pattern.
if (windowHash === patternHash) {
return 0; // Pattern found at the beginning of the stream
}
// Initialize variables for window management.
let currentIndex = 1; // Index of the first element in the current window
const unsetMask = (1 << (pattern.length - 1)) - 1; // Mask to unset the largest bit
while (true) {
// Unset the largest bit from the window hash, representing the element leaving the window.
windowHash &= unsetMask;
windowHash <<= 1; // Shift the window hash to the left
// Get the next element from the stream and update the window hash.
const current = stream.next();
if (current === 1) {
windowHash |= 1; // Set the least significant bit if the element is 1
}
// Check if the current window matches the pattern.
if (windowHash === patternHash) {
return currentIndex; // Pattern found at the current index
} else {
currentIndex++; // Move the window forward
}
}
}
// Initialize the stream and pattern
const stream = [1, 1, 1, 0, 1, 1, 1];
const pattern = [0, 1];
// Create an InfiniteStream object
const infiniteStream = new InfiniteStream(stream);
// Find the pattern in the stream
const index = findPattern(infiniteStream, pattern);
// Print the result
if (index !== -1) {
console.log("Pattern found at index " + index);
} else {
console.log("Pattern not found");
}
Output
Pattern found at index 3
Time complexity: O(N)
Auxiliary Space: O(M)