题目重点：Coding 题目给有序食材列表和连续序列菜谱，并追问 O(1) 空间、流式输入；本文用逐菜谱 KMP 状态处理精确连续匹配。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 菜谱是具体食材 token 的有序数组，完整且连续地出现在总列表中即返回 true；不允许跳过食材，也不要求覆盖总列表。
- 空菜谱按常见字符串匹配约定为 true；每条菜谱只需知道是否至少出现一次，不返回全部位置。
- 训练版 KMP 为每条非空菜谱保存前缀表 O(m)；题目 O(1) 额外空间追问可用每条菜谱朴素滑窗复扫来满足，但时间退化。
解题路线
- 先澄清“连续”是菜谱 token 在输入中相邻出现；对每条菜谱用 KMP 前缀表描述部分匹配长度。
- 顺序消费食材；当前 token 不匹配时按 pi 回退状态，匹配时递增，达到菜谱长度即标记 found。食材可逐个到达，不需要保留历史输入。
- 若严格要求 O(1) 额外空间且输入可重读，对每个起点做朴素逐项对照，最坏 O(Nm)；单向不可重放流要同时支持任意长模式，无法普遍保持 O(1) 状态。
- 多菜谱时为每条维护状态，时间 O(NR+Σm_i)；若 R 很大，可把菜谱建成 Aho–Corasick 自动机共享扫描。
- 用穷举所有连续切片作独立参考，对 10,000 组重复 token、空列表和多菜谱随机数据验证。
手动走一遍
食材 [a,b,a,b,c]，菜谱 [a,b,c] 与 [a,c]：前者从下标 2 开始连续出现，后者不存在。KMP 处理前两个 a,b 匹配失败后的前缀回退，再在后半段命中。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Match each recipe as an exact contiguous ingredient sequence."""
def prefix_table(pattern: list[str]) -> list[int]:
pi = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j and pattern[i] != pattern[j]:
j = pi[j - 1]
if pattern[i] == pattern[j]:
j += 1
pi[i] = j
return pi
class RecipeMatcher:
def __init__(self, recipe: list[str]):
self.recipe = recipe[:]
self.pi = prefix_table(recipe)
self.state = 0
self.found = not recipe
def feed(self, ingredient: str) -> bool:
if self.found or not self.recipe:
return self.found
while self.state and ingredient != self.recipe[self.state]:
self.state = self.pi[self.state - 1]
if ingredient == self.recipe[self.state]:
self.state += 1
if self.state == len(self.recipe):
self.found = True
return self.found
def match_recipes(ingredients: list[str], recipes: list[list[str]]) -> list[bool]:
matchers = [RecipeMatcher(recipe) for recipe in recipes]
for ingredient in ingredients:
for matcher in matchers:
matcher.feed(ingredient)
return [matcher.found for matcher in matchers]
复杂度
R 条菜谱总长度 M、输入长 N：前缀表 O(M)，逐 token 更新所有状态 O(NR) 摊还时间、O(M+R) 空间；匹配一个菜谱为 O(N+m)。若只求一次性 O(1) 额外空间的朴素版，最坏 O(Nm)。
易错点与追问
容易失分的边界
- 把有序但不相邻的子序列当成连续菜谱。
- 声称 KMP 不保存任何额外状态；模式前缀表需要 O(m) 空间。
- 流式场景把全部历史食材缓存在内存，失去流处理意义。
- 有大量菜谱时逐条扫描却宣称总时间仍 O(N+M)。
继续深挖
- 如果菜谱可包含通配符或可替代食材，自动机如何改变？
- 如果要报告所有命中位置，找到首个后状态应怎样回退？
- 百万条菜谱怎样构建共享索引并分片流处理？
- 题面若真要求多个菜谱按顺序拼接成整个列表，与子串匹配有什么区别？
