字符串匹配之 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 

阅读全文…