KMP算法快速理解

一、最长公共子缀

公共子缀分为前缀和后缀
前缀：总是包含第一个字符的子串（不包括父串本身）
后缀：总是包含最后一个字符的子串（不包括父串本身）
————————————————————————————
举个例子：
父串ABCDEAB
前缀：A、AB、ABC、ABCD、ABCDE、ABCDEA
后缀：B、AB、EAB、DEAB、CDEAB、BCDEAB
最长公共子缀就是指完全相同的最长前缀和后缀
在上述的例子中最长公共子缀是AB，长度为2。
如下图所示，最长公共子缀就是看前、后有多少完全相同的字符。

二、next数组

next数组的值其实就是【当前位置之前的字符串】的最长公共子缀长度
————————————————————————————
举个例子：
父串ABAABACA
当我们在计算C字符对应的next数组值时，我们其实就是要计算ABAABA这个字符串的最长公共子缀。
ABAABA的前缀有A、AB、ABA、ABAA、ABAAB
                  后缀有A、BA、ABA、AABA、BAABA
最长的公共子缀是ABA，长度为3，所以C这个位置的next数组值就是3。
由于第一个字符之前没有任何字符，所以我们规定第一个字符处的next数组值为-1；第二个字符之前只有1个字符，但是我们规定子缀是不能包含父串本身的，所以最长公共子缀为0；其他位置的按照标准计算即可。
根据定义，父串ABAABACA的next数组值为：

i	0	1	2	3	4	5	6	7
str[i]	A	B	A	A	B	A	C	A
next[i]	-1	0	0	1	1	2	3	0

三、基于next数组的文本匹配

KMP算法解决的问题是在父串中查找子串是否存在。
————————————————————————————
我们举例来说明KMP的工作过程
父串txt=BBCABCDABEABCDABCDABDE
子串str=ABCDABD
（1）求出子串str的next数组

i	0	1	2	3	4	5	6
str[i]	A	B	C	D	A	B	D
next[i]	-1	0	0	0	0	1	2

（2）指针定位到父串的开头和子串的开头，匹配第一个字符

（3）子串第一个字符就不匹配，子串不动，父串移动，继续和子串第一个字符匹配

（4）子串第一个字符仍然不匹配，子串不动，父串移动，继续和子串第一个字符匹配

（5）子串第一个字符仍然不匹配，子串不动，父串移动，继续和子串第一个字符匹配

（6）子串第一个字符匹配了，则子串和父串同时向后移动，继续匹配，直到匹配到子、父串不相等（或者子串匹配完成，则查找结束）

（7）匹配到不相等的位置，该位置在子串中的下标是i，则父串不动，子串向左移动i-next[i]个位置，比如图中位置D在子串中下标是6，next[6]=2，则子串向左移动6-2=4个位置。

（8）继续比较当前位置的子串是否和父串相等，如果等则子串、父串一起后移；如果不等则重复上面的过程，也就是左移i-next[i]个位置

（9）左移完之后继续比较子串是否和父串相等，发现不等，这时发现子串已经回到了头部，再左移没有位置移动了，所以此时只移动父串，继续和子串第一个位置比较

（10）发现父串和子串第一个位置相同，则父串、子串一起向后移动，直到匹配到不相同的字符（或者子串匹配完成，则查找结束）

（11）发现了不相等的字符，则子串向左移动i-next[i]个字符

（12）移动之后继续匹配，如果相等就父串、子串一起往后动；如果不等就子串左移i-next[i]个字符；如果已经回退到子串头部了，那就只移动父串就好

（13）子串已经匹配完了，查找结束。

所以KMP的基本工作原理就是：

1.如果子串在头部，则：

• 若子串、父串相等，则同时往后移动
• 若子串、父串不等，则父串往后移动

2.如果子串不在头部，则：

• 若子串、父串相等，则同时往后移动
• 若子串、父串不等，则子串往左移动i-next[i]个位置

四、KMP工作原理
你应该发现，KMP的核心要义其实就是左移i-next[i]这个部分了，那为什么这个部分可以帮助我们减少比较的工作量呢？
传统的匹配算法如下图：

在匹配到不相同的字符时，父串回退到刚才开始匹配位置的下一个位置，子串回退到头部，从头开始匹配。
我们明显觉得很麻烦，甚至可以喊一声：你要退也退到一个跟子串开头字符相等的位置吧，干嘛非得一位一位动？

就比如下图，我们在父串E位置匹配失败了，如果要重新匹配，那肯定也是从刚才匹配过的字符中找一个跟子串头位置相等的位置，比如标红的A处开始重新匹配吧，那为什么移动i-next[i]就正好能找到这个位置呢？

回顾一下next数组的含义：next[i]指的是【i之前的字符串】的最长公共子缀长度。

next数值告诉了我们两个信息，一是子串从哪个位置开始和头部相等，二是从那个位置开始，到当前位置结束，一共有多少个相同的字符和头部是匹配的。
比如上图位置D，next[6]=2，就代表str[6-2]=str[4]这个位置是跟头部字符是相同的；而从str[4]这个位置开始，有2个字符和从头部开始有2个字符时相同的。
从子串开头开始有X₀X₁两个字符和D前面两个字符X₄X₅相等，既然X₀X₁=X₄X₅，现在X₆和父串不相等，那我们下一步就应该看看X₃和父串对应位置是否相等。