题目重点：点号按字面处理，独立核对通配匹配和短请求窗口，不让被屏蔽请求消失。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练最近5次包含当前请求；题目未明确当前是否算入，正式题须核对，前5次口径作为待核变体。
- 所有请求进入频次窗口，不以是否blocked过滤；*匹配任意长度字符串含空串，完全匹配整个IP文本。
- 不进行IP规范化或octet范围校验，题目把IP作为字符串，点号仍是字面。
解题路线
- star_match用DP，previous[i]表示此前pattern可匹配text前i字符。普通字符来自previous[i-1]且字面相等；*来自previous[i]（空）或current[i-1]（多吃一个）。
- 初始化空pattern只匹配空text，*可以让current[0]延续空匹配。逐行只存两个长度L+1向量，支持连续多个*而不依赖正则特殊符号处理。
- 窗口deque维护最近5个请求，Counter同步增减；先放当前，再在超5时删最老项。blocked=黑名单任一匹配或counts[current]>2。
- 两层规则独立：黑名单命中依然应进入窗口计数，不能early return漏记请求。若实际合同是“之前5个”，应先查询过去窗口后插当前，而不是只改阈值。
- 模式量很大可预编译自动机/索引与cache，但缓存匹配结果不缓存请求限频结果，后者随历史变化；本训练基线先把语义核对正确。
手动走一遍
训练pattern="121.*"能匹配"121.3"，不能匹配"121X3"；requests=[a,a,a,b,c,a]最近5含当前时第3个a blocked，最后窗口[a,a,b,c,a]也blocked；若是前5合同，第3个尚只有2次历史a会不blocked。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import Counter,deque
def star_match(text,pattern):
"""Only * is special; . and every other character are literal."""
previous=[True]+[False]*len(text)
for ch in pattern:
current=[previous[0] and ch=='*']+[False]*len(text)
for i,value in enumerate(text,1):
current[i]=(previous[i] or current[i-1]) if ch=='*' else previous[i-1] and ch==value
previous=current
return previous[-1]
def blocking_flags(requests,blacklist):
"""Recent five includes current request, all requests count including blocked ones."""
window=deque()
counts=Counter()
output=[]
for ip in requests:
window.append(ip)
counts[ip]+=1
if len(window)>5:
removed=window.popleft()
counts[removed]-=1
if not counts[removed]:del counts[removed]
output.append(int(counts[ip]>2 or any(star_match(ip,pattern) for pattern in blacklist)))
return output
复杂度
请求N、模式P、平均文本L、pattern长M，DP匹配最坏O(N·P·L·M)，O(L)临时空间；窗口更新期望O(1)、大小≤5。提前规范化或自动机需另述成本。
易错点与追问
容易失分的边界
- 点号当正则任意字符。
- blocked请求不进窗口。
- 每IP最近5条代替全局最近5请求。
- 前5和含当前5混淆。
继续深挖
- 前5口径怎样写独立测试？
- IPv6不同写法是否规范化？
- 许多pattern怎样预处理而不引入regex注入？
