存档

  • 字符串匹配之 KMP 算法

    某天在群里看到 井大侠 提起传说中的“看毛片”算法,在网上搜到一篇好文章(见参考资料 [1]),发现从有限状态自动机的角度来理解可能会更容易一些。

    简单的逐个字符比较

    最简单的匹配算法是将两个字符串第一个字符对齐,然后开始逐字符比较。当在某个位置发现不匹配时,把模式串向右移动一个字符,再从模式串的第一个字符开始与主串对应位置的字符开始比较。例如要从字符串 T 中查找模式串 P,比较过程如下:

                            1                   2
    pos 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
    T   A B C Z 

    阅读全文…

    2011年6月3日 | 归档: 数据结构与算法 | 标签: ,
文章标签 ‘kmp’