2020-2021:teams:legal_string:jxm2001:字符串_4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:字符串_4 [2020/09/04 11:24] jxm2001 [算法练习] |
2020-2021:teams:legal_string:jxm2001:字符串_4 [2020/09/04 11:28] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 312: | 行 312: | ||
| 由于当前串的后缀与当前等价类地某个串匹配，而该等价类的最短串长度大于父节点等价类中最长串，于是当前串一定能与父节点最长串匹配。 | 由于当前串的后缀与当前等价类地某个串匹配，而该等价类的最短串长度大于父节点等价类中最长串，于是当前串一定能与父节点最长串匹配。 | ||
| - | 于是跳 $\text{parent}$ 树过程中如果遇到 $ch[pos][c]$ 存在的情况，匹配长度变为 $len_\text{pos}+1$。 | + | 于是跳 $\text{parent}$ 树过程中如果遇到 $ch[pos][c]$ 存在的情况，则跳到 $ch[pos][c]$ 结点，匹配长度变为 $len_\text{pos}+1$。 |
| 每次失配向上跳使得匹配长度变短，而匹配长度最多增加 $|T|$ 次，于是失配的均摊复杂度为 $O(1)$。总时间复杂度 $O(n)$。 | 每次失配向上跳使得匹配长度变短，而匹配长度最多增加 $|T|$ 次，于是失配的均摊复杂度为 $O(1)$。总时间复杂度 $O(n)$。 | ||
2020-2021/teams/legal_string/jxm2001/字符串_4.1599189848.txt.gz · 最后更改: 2020/09/04 11:24 由 jxm2001
