3037：在无限流中寻找模式 II（★★）

力扣第 3037 题

题目

给定一个二进制数组 pattern 和一个类 InfiniteStream 的对象 stream 表示一个下标从 0 开始的二进制位无限流。

类 InfiniteStream 包含下列函数：

• int next()：从流中读取 一个 二进制位 （是 0 或 1）并返回。

返回 第一个使得模式匹配流中读取的二进制位的 开始下标。例如，如果模式是 [1, 0]，第一个匹配是流中的高亮部分 [0, 1, 0, 1, ...]。

示例 1：

输入: stream = [1,1,1,0,1,1,1,...], pattern = [0,1]
输出: 3
解释: 模式 [0,1] 的第一次出现在流中高亮 [1,1,1,0,1,...]，从下标 3 开始。

示例 2：

输入: stream = [0,0,0,0,...], pattern = [0]
输出: 0
解释: 模式 [0] 的第一次出现在流中高亮 [0,...]，从下标 0 开始。

示例 3：

输入: stream = [1,0,1,1,0,1,1,0,1,...], pattern = [1,1,0,1]
输出: 2
解释: 模式 [1,1,0,1] 的第一次出现在流中高亮 [1,0,1,1,0,1,...]，从下标 2 开始。

提示：

• 1 <= pattern.length <= 104
• pattern 只包含 0 或 1。
• stream 只包含 0 或 1。
• 生成的输入使模式的开始下标在流的前 105 个二进制位中。

相似问题：

• 3621：位计数深度为 K 的整数数目 I（2330 分）

分析

• kmp 找第一个完全匹配的下标即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def findPattern(self, stream: Optional['InfiniteStream'], pattern: List[int]) -> int:
        A = pattern+[2]
        pi,j = [0],0
        for i in range(1,len(A)):
            while j>0 and A[i]!=A[j]:
                j = pi[j-1]
            j += A[i]==A[j]
            pi.append(j)
        while True:
            c = stream.next()
            while j>0 and c!=A[j]:
                j = pi[j-1]
            j += c==A[j]
            pi.append(j)
            A.append(c)
            if j==len(pattern):
                return len(A)-j*2-1

2339 ms