知识卡片
滚动更新移出首位移入末位
窗口从s移到s+1时,先从数值t_s中减去最高位字符的权值,再乘进制d并加新末位字符。
预先算好d^{m−1}后,每次滑动只需常数次算术操作;若数值超出机器字,仍要另计大整数成本。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
, tn–m in Θ(n – m) time, observe that you can compute ts+1 from ts in constant time, since Subtracting 10m−1T [s + 1] removes the high-order digit from ts, multiplying the result by 10 shifts the number left by one digit position, and adding T[s + m + 1] brings in the appropriate low-order digit. For example, suppose that m = 5, ts = 31415, and the new low-order digit is T[s + 5 + 1] = 2. The high-order digit to remove is
参考来源
- 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[10000,15000))。
- 结论依据:原文定义字符串匹配、前后缀或相应算法的比较规则;相关图式已核对。
- 原始内容:To compute the remaining values t 1 , t 2 , …, t n – m in Θ( n – m ) time, observe that you can compute t s +1 from t s in constant time, since Subtracting 10 m −1 T [ s + 1] removes the high-order digit from t s , multiplying the result by 10 shifts the number left by one digit position, and adding T [ s + m + 1] brings in the appropriate low-order digit. For example, suppose that m = 5, t s = 31415, and the new low-order digit is T [ s + 5 + 1] = 2. The high-order digit to remove is