目录

一个例子来直观地认识

为什么是最大公共前后缀

KMP算法的使用

如何求next函数值

改进

写在后面：

---

一个例子来直观地认识

假设主串为,模式串为

当遇到下面如图这种情况：主串第个字符和模式串第个字符失配时

主串

主串前面(无关紧要)

最

大

公

共

前

后

缀

乱

七

八

糟

最

大

公

共

前

后

缀

s_i

模式串

最

大

公

共

前

后

缀

乱

七

八

糟

最

大

公

共

前

后

缀

p_j

 可以将模式串这样滑动

主串

主串前面(无关紧要)

最

大

公

共

前

后

缀

乱

七

八

糟

最

大

公

共

前

后

缀

模式串

最

大

公

共

前

后

缀

乱

七

八

糟

最

大

公

共

前

后

缀

 显然，这样右滑一个然后比较没什么意义，在最朴素的模式匹配算法中就是这么做的。

对于这么一种情况，朴素的做法还会有很多余的做法

主串

主串前面(无关紧要)

最

大

公

共

前

后

缀

乱

七

八

糟

最

大

公

共

前

后

缀

模式串

最

大

公

共

前

后

缀

乱

七

八

糟

最

大

公

共

前

后

缀

 

主串

主串前面(无关紧要)

最

大

公

共

前

后

缀

乱

七

八

糟

最

大

公

共

前

后

缀

模式串

最

大

公

共

前

后

缀

乱

七

八

糟

最

大

公

共

前

后

缀

 一直到

 

主串

主串前面(无关紧要)

最

大

公

共

前

后

缀

乱

七

八

糟

最

大

公

共

前

后

缀

模式串

最

大

公

共

前

后

缀

乱

七

八

糟

最

大

公

共

前

后

缀

既然一个一个右滑效率很低，那么应该怎么右滑呢？

我们发现，已知最大公共前后缀的时候，依据最大公共前后缀的情况可以找到那个合适的右滑举例

在代码实现的过程中，我们让模式串的“右滑”操作是通过指针实现的

经过这种后公共前后缀一定是相等的，无需再比较一遍，指针应该跳到的位置是模式串的最大公共前后缀中的前缀后面那一位。

从人的角度思考，“右滑”更容易理解。但对于机器，应该考虑的是失配后模式串指针应该指向哪里。 

这两种表述是等价的。

右滑多少？主串中第个字符和模式串中第个字符失配后，主串中第个字符应该和模式串中那个字符比较？

 

为什么是最大公共前后缀

上面我突兀地讲到了“最大公共前后缀”，这里便是为什么是“最大公共前后缀”。

 希望下面的图片能够帮助您理解。

主串

主串前面(无关紧要)

最

大

公

共

前

后

缀

乱

七

八

糟

最

大

公

共

前

后

缀

第i个字符

模式串

最

大

公

共

前

后

缀

乱(我们假设的第k个字符)

七

八

糟

最

大

公

共

前

后

缀

 其实next数组存的就是我们那个k值。

除了最大公共前后缀地长度加1，还有两种情况。

如果模式串第1个字符和主串第i个字符失配，就让主串地i加1。但这个加很巧妙，让next[j]=0,这样经过i++，j++之后，主串的i加了一，模式串的j又指向了第一个字符，从第一个开始比较。

如果没有公共最大前后缀，那匹配过的这一段没啥意义了，j直接从1开始吧。

KMP算法的使用

如何求next函数值

改进

写在后面：

我找不到更好地语言来表述kmp算法以及它的实现

通俗便会不严谨，这些晦涩的语言就像是数学里面的证明一样

而是实现的这个代码也已经足够简洁优美突出本质

所以我便直接截图，这些内容来自严蔚敏的《数据结构（C语言版）》

我觉得这篇博客比较好的是自己找的那个例子，相对于简单的字符串的例子更容易去理解教材上看起来晦涩的语言