题目重点：模式完整匹配输入，first与longest两种规则不可混称同一答案。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 字面字符0/1，*匹配任意长度含空串；不是正则里的单字符点号。
- 训练policy=first按配置顺序；longest按模式原字符串长度并列顺序，所谓“最具体”可能应计字面数而非长度，正式定义仍待核。
解题路线
- DP[i,j]表示pattern前i项完整匹配text前j字符。字面匹配从左上转移；*可匹配空从上一行同列，或多一个字符从当前行左列。
- 逐行滚动，把前一行保存不覆盖。空输入只可由全部*匹配。先验证每个模式是否匹配，再按显式胜出规则选值。
- AI重建例含逻辑矛盾，不能把其同义说明当可靠规范。特别10001不能匹配*11，因为末尾不是11；题目训练的实际matcher应独立核对。
手动走一遍
10*1匹配10001，*11不匹配10001；111匹配*11。rules=[(*,A),(1*,B)]、input1：first返回A；longest返回B，所以选胜规则决定结果。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def glob_match(pattern,text):
if any(c not in '01*' for c in pattern) or any(c not in '01' for c in text):raise ValueError("binary literals and star only")
previous=[True]+[False]*len(text)
for token in pattern:
current=[False]*(len(text)+1)
if token=='*':current[0]=previous[0]
for j,c in enumerate(text,1):
current[j]=(previous[j] or current[j-1]) if token=='*' else previous[j-1] and token==c
previous=current
return previous[-1]
def match_rules(rules,text,policy='first'):
if policy not in ('first','longest'):raise ValueError("explicit winner policy required")
matches=[(i,p,value) for i,(p,value) in enumerate(rules) if glob_match(p,text)]
if not matches:return None
winner=matches[0] if policy=='first' else min(matches,key=lambda row:(-len(row[1]),row[0]))
return winner[2]
复杂度
单模式长P、输入长N，O(PN)时间/O(N)空间；R规则总O(NΣP)。高频查询才考虑联合NFA/DFA，其状态数与优先策略需额外分析。
易错点与追问
容易失分的边界
- 把*当任一单字符会漏空/多字符。
- “最长匹配”可能指pattern长度、字面数、匹配文本长，完整匹配下最后一种都相同，必须问清。
继续深挖
- 支持单字符?时递推如何改？
- 为什么不能直接拿字符串AC automaton当任意长度*的通用解？
