新闻动态

动作序列匹配怎样利用已匹配的前后缀:独立推演第01例

2026-11-17 1

在一长串动作中寻找一个短模式时,失败后完全从头比较会重复许多工作。已经匹配的末尾部分,有时也恰好是模式的开头,可以保留这部分进度继续检查。

明确本例规则

本例先为模式的每个前缀计算最长相同的真前缀与后缀长度。扫描输入时,当前字符不匹配就沿此前缀表回退;匹配则增加长度。找到完整模式后,记录起点,再退到完整模式的最长真前后缀,继续寻找可能重叠的出现。

输入与逐步结果

模式BAABAC;输入CCBABABBCBAABACBAABACCABBBBAB。

最长真前后缀长度表:[0, 0, 0, 1, 2, 0] 位置 | 字符 | 原进度 | 回退链 | 命中 | 保留进度 [0, 'C', 0, [], False, 0] [1, 'C', 0, [], False, 0] [2, 'B', 0, [], False, 1] [3, 'A', 1, [], False, 2] [4, 'B', 2, [0], False, 1] [5, 'A', 1, [], False, 2] [6, 'B', 2, [0], False, 1] [7, 'B', 1, [0], False, 1] [8, 'C', 1, [0], False, 0] [9, 'B', 0, [], False, 1] [10, 'A', 1, [], False, 2] [11, 'A', 2, [], False, 3] [12, 'B', 3, [], False, 4] [13, 'A', 4, [], False, 5] [14, 'C', 5, [], True, 0] [15, 'B', 0, [], False, 1] [16, 'A', 1, [], False, 2] [17, 'A', 2, [], False, 3] [18, 'B', 3, [], False, 4] [19, 'A', 4, [], False, 5] [20, 'C', 5, [], True, 0] [21, 'C', 0, [], False, 0] [22, 'A', 0, [], False, 0] [23, 'B', 0, [], False, 1] [24, 'B', 1, [0], False, 1] [25, 'B', 1, [0], False, 1] [26, 'B', 1, [0], False, 1] [27, 'A', 1, [], False, 2] [28, 'B', 2, [0], False, 1] 全部匹配起点:[9, 15]

编号仅标识本次案例中的对象,不能把它当成重要性排名。复算时先保留原输入,再按表格顺序记录中间状态。零值、空列表和未到达各有含义,不能因为显示相似就合并处理。需要分数的地方保存精确值,小数只用于阅读。

结果如何核对

真前缀不包含整个字符串本身。匹配起点从零编号,长度固定;每个起点截取出的片段必须与模式完全相同。表格列出前缀表和扫描每个字符后的保留长度,并在命中位置注明完整匹配。

用逐个起点的直接切片比较可以复核全部命中。尤其要保留重叠出现,不能找到一次后跳过整段长度,否则会漏掉模式后缀与下次前缀共用输入的情况。回退只是复用知识,不会改变原始动作顺序。

使用边界

字母仅表示三类抽象输入,本例没有时间窗口、通配符或同时按键。若不同动作被映射成同一个符号,匹配结果也随之改变。模式不能为空,空模式应由调用方另行定义,不能直接塞进本例循环。

练习可以先保持其他条件不变,只调整一项输入,观察哪个中间步骤首先产生差异。如果结果不同,先确认单位、端点和同值处理是否一致,再查具体运算。最终答案应与输入和过程一起保存,才方便判断这份结论适用于什么情境。