知识卡片

普通读书笔记卡 · 3705.a.1

拉宾卡普滚动保持窗口指纹不变式

理解等级:中级

每次进入位移s的检查时,滚动值t_s必须等于当前长度m文本窗口的数值模q。预处理算初始指纹和最高位权值;每次滑动按递推式更新,保证下轮哈希筛选的是正确窗口。

这张卡片看不懂?

已有反馈 · 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