Find pattern in infinite stream i

Array Sliding Window Rolling Hash String Matching Interactive Hash Function

56.9% acceptance

Mar 31, 2026

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, ...].

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

/**
 * Definition for an infinite stream.
 * impl InfiniteStream {
 *     pub fn new(bits: Vec<i32>) -> Self {}
 *     pub fn next(&mut self) -> i32 {}
 * }
 */
impl Solution {
  pub fn find_pattern(mut stream: InfiniteStream, pattern: Vec<i32>) -> i32 {
    // KMP algorithm to find pattern in stream
    let m = pattern.len();
    // Build failure function
    let mut fail = vec![0i32; m];
    let mut k = 0i32;
    for i in 1..m {
      while k > 0 && pattern[k as usize] != pattern[i] {
        k = fail[(k - 1) as usize];
      }
      if pattern[k as usize] == pattern[i] {
        k += 1;
      }
      fail[i] = k;
    }
    // Search in stream
    let mut j = 0i32;
    let mut idx = 0i32;
    loop {
      let bit = stream.next();
      if pattern[j as usize] == bit {
        j += 1;
      } else {
        while j > 0 && pattern[j as usize] != bit {
          j = fail[(j - 1) as usize];
        }
        if pattern[j as usize] == bit {
          j += 1;
        }
      }
      if j == m as i32 {
        return idx - m as i32 + 1;
      }
      idx += 1;
    }
  }
}