知识卡片
拉宾卡普滚动保持窗口指纹不变式
每次进入位移s的检查时,滚动值t_s必须等于当前长度m文本窗口的数值模q。预处理算初始指纹和最高位权值;每次滑动按递推式更新,保证下轮哈希筛选的是正确窗口。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
The for loop of lines 7–12 iterates through all possible shifts s, maintaining the following invariant: Whenever line 8 is executed, ts = T[s + 1:s + m] mod q. If a hit occurs because p = ts in line 8, then line 9 determines whether s is a valid shift or the hit was spurious via the test P[1:m] == T[s +1:s +m]. Line 10 prints out any valid shifts that are found. If s < n – m (checked in line 11), then the for
参考来源
- 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[15000,20000))。
- 结论依据:原文第32.2–32.3节对应算法、定义或复杂度说明;公式与示意图已核对。
- 原始内容:The for loop of lines 7–12 iterates through all possible shifts s , maintaining the following invariant: Whenever line 8 is executed, t s = T [ s + 1: s + m ] mod q . If a hit occurs because p = t s in line 8, then line 9 determines whether s is a valid shift or the hit was spurious via the test P [1: m ] == T [ s +1: s + m ]. Line 10 prints out any valid shifts that are found. If s < n – m (checked in line 11), then the for