严蔚敏 数据结构 kmp算法详解.pdf

算法原理： KMP 算法使用一个称为 失配表（failure function） 的预处理表来提高匹配效率。失配表存储了模式串中每个字符失配后应该跳转到的位置。 在匹配过程中，算法将模式串和文本串逐个字符进行比较。如果字符匹配，则继续比较下一个字符。如果字符不匹配，则算法使用失配表跳转到模式串中适当的位置，然后继续比较。 失配表的构造： 失配表 F[i] 表示模式串的第 i 个字符失配后应该跳转到的位置。失配表的构造过程如下： 初始化 F[0] = 0。 对于模式串的每个字符 i（从 1 开始）： 如果模式串的第 i 个字符与第 F[i-1] 个字符匹配，则 F[i] = F[i-1] + 1。 否则，查找模式串中与第 i 个字符匹配的最长前缀，并令 F[i] 等于该前缀的长度。