字符流检词并删除：后缀命中、长词优先与连锁删除

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 非空词集合，push一次一个字符；同次多个后缀命中时最长词优先，同长词字典序。
• 训练版允许删除后连锁后缀检测，返回本次全部删除词列表。实际要求仅返回一个、最早词优先等未明确。

解题路线

1. 保留字符stack，新字符加入后只需检查词是否为当前后缀。此前无未处理匹配的不变量，使任何新产生的匹配必须涉及新尾部。
2. 命中就删后缀并再次检查。稳定后buffer不含需处理后缀；长词优先政策防ab与b同时命中时结果随set迭代顺序变。
3. 基线逐词逐字符比对清楚但成本高。可反向Trie限制查看最长词尾；Aho–Corasick加状态栈能在删除后恢复前一位置自动机状态，仍要证明与选择政策一致。

手动走一遍

words={ab,b}，流a再b，第二次删ab，buffer空；若短词优先会只删b留下a，是不同合同。连续字符输入的已删内容不会参与下一次匹配；对原始完整流搜索不能表示删除后的状态。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class Filter:
    def __init__(self,words):
        if any(not word for word in words):raise ValueError("empty word")
        self.words=sorted(set(words),key=lambda w:(-len(w),w));self.buffer=[]
    def push(self,char):
        if len(char)!=1:raise ValueError("one character required")
        self.buffer.append(char);removed=[]
        # Longest suffix wins; delete repeatedly to support explicit cascades.
        while True:
            matched=next((w for w in self.words if len(w)<=len(self.buffer)
                         and self.buffer[-len(w):]==list(w)),None)
            if matched is None:return removed
            del self.buffer[-len(matched):];removed.append(matched)
    def text(self):return "".join(self.buffer)

复杂度

最大词长M、词数D、字符数L。一次suffix扫描O(DM)，每次成功删至少1字符，整体O(LDM)基线；词表+buffer O(totalWordLength+L)。

易错点与追问

容易失分的边界

• 空词会导致永不推进的删除循环。
• 用字符串replace会删非尾部或所有实例，改变在线匹配顺序。

继续深挖

• 返回单个词但可连锁删除时，应该返回首个还是全部事件？
• 状态栈自动机怎样在删掉k字符后O(k)回退？