大话数据结构十一：字符串的模式匹配（KMP算法）

大话数据结构十一：字符串的模式匹配（KMP算法）2014-12-301. KMP算法简介：

kmp算法是一种改进的字符串匹配算法，相比朴素算法，KMP算法预先计算出了一个哈希表，用来指导在匹配过程中匹配失败后尝试下次匹配的起始位置，以此避免重复的读入和匹配过程。这个哈希表被称为"部分匹配值表"（Particial match table），这种设计是KMP算法最精妙之处。

2. KMP算法分析：

下面以阮一峰老师博客中的一篇文章来分析KMP算法的原理：有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？

（1）首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

（2）因为B与A不匹配，搜索词再往后移。

（3）就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

（4）接着比较字符串和搜索词的下一个字符，还是相同。

（5）直到字符串有一个字符，与搜索词对应的字符不相同为止。

（6）这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。