2020-2021:teams:legal_string:jxm2001:字符串_4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:字符串_4 [2020/09/02 19:57] jxm2001 |
2020-2021:teams:legal_string:jxm2001:字符串_4 [2020/09/04 11:28] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 310: | 行 310: | ||
| 如果存在 $ch[pos][c]$，则直接匹配，且匹配长度 $+1$。否则考虑尽可能地保留后缀，于是不断跳 $\text{parent}$ 树。 | 如果存在 $ch[pos][c]$，则直接匹配，且匹配长度 $+1$。否则考虑尽可能地保留后缀，于是不断跳 $\text{parent}$ 树。 | ||
| - | 由于当前串的后缀与当前等价类地某个串匹配，而该等价类的最短串长度大于其父节点的等价类中的最长串，于是当前串一定能与父节点最长串匹配。 | + | 由于当前串的后缀与当前等价类地某个串匹配，而该等价类的最短串长度大于父节点等价类中最长串，于是当前串一定能与父节点最长串匹配。 |
| - | 于是跳 $\text{parent}$ 树过程中如果遇到 $ch[pos][c]$ 存在的情况，匹配长度变为 $len_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.1599047871.txt.gz · 最后更改: 2020/09/02 19:57 由 jxm2001
