KMP查询算法的匹配串的前缀后缀相同的最大长度

一、KMP算法的作用

查询复杂度是O(n+m)，其中n是主字符串长度，m是匹配串的长度。

二、字符串的前缀和后缀

(一)前缀

指的是字符串从第1个字符串开始，每次截取连续字符串的操作。

例如字符串"ABC"的前缀有下列情况：

"A"、"AB"、"ABC"。

(二)后缀

指的是从第1个字符开始，每次截取连续字符串到最后1个字符的操作。

例如字符串"ABC"的后缀有下列情况：

"ABC"、"BC"、"C"。

三、匹配串的前缀和后缀相同

简单的说：就是把前缀和后缀拿来比较，有相同的就记录前缀或者后缀的长度。

案例(避免选择整个字符串为前缀和后缀)：

以匹配串"ABAB" 为例：

比较1个字符：前缀"A"和后缀"B"不相同。
比较2个字符：前缀"AB"和后缀"AB"相同，记录前缀长度是2个字符。
比较3个字符：前缀"ABA"和后缀"BAB"不相同。

四、KMP比较的思路

(一)预处理，求得匹配串每个字符前面的前缀和后缀相同的最长长度。

默认值是0，也就是从匹配串的第1个字符开始比较。

(二)按顺序从第1个位置比较主串和匹配串的对应字符

1、如果对应位置的字符相同，去下一个位置比较。

2、如果比较到匹配串的末尾，代表匹配成功。

3、如果对应字符不相等，就把匹配串跳转到前缀后缀相同的长度，继续比较。

总之，前面有比较过并且相同的，就不需要从头开始比较了。