← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3704.a

匹配成本分预处理与扫描两段

理解等级:中级

多数匹配算法先根据模式建立辅助信息,再扫描文本找有效位移;总时间是预处理与匹配时间之和。

比较算法时应同时列出两段成本,尤其在同一模式要匹配多份文本时,预处理可以复用。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第32章 字符串匹配 · 查看原书依据

      Except for the naive brute-force algorithm in Section 32.1, each string-matching algorithm in this chapter performs some preprocessing based on the pattern and then finds all valid shifts. We call this latter phase “matching.” Here are the preprocessing and matching times for each of the string-matching algorithms in this chapter. The total running time of each

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[0,5000))。 - 结论依据:原文定义字符串匹配、前后缀或相应算法的比较规则;相关图式已核对。 - 原始内容:Except for the naive brute-force algorithm in Section 32.1 , each string-matching algorithm in this chapter performs some preprocessing based on the pattern and then finds all valid shifts. We call this latter phase “matching.” Here are the preprocessing and matching times for each of the string-matching algorithms in this chapter. The total running time of each