next数组算法

A. KMP 算法中 next 数组手工求解

KMP算法是一种改进的字符串匹配算法，如果不研究编码的话，手工实现还是比较简单，小型字符串甚至不需要你去求 next 数组就能看出来怎么移动。但是会有一些题目让你求解 next 数组，这里就以一个题目讲一下手工求解的过程。

例：求串 ‘ababaaababaa’ 的 next 数组

观察第一个元素，它没有前缀和后缀（串本身不能作为前缀或后缀），所以记录数据为0（这个数字表示当存在前缀和后缀相同的情况下，所能包含的最大的元素）

观察前两个元素，前缀为a，后缀为b，不相同，即没有相同的前缀和后缀，所以同样记录数据为0

观察前三个元素，存在前后缀相同的情况，为a，记录数据为1

观察前四个元素，同样存在前缀后缀相同的情况，为ab，记录数据为2

观察第五个元素，相同的前后缀为aba（ aba ba、ab aba ），记录数据为3

同理观察余下的（用加粗表示前缀、下划线表示后缀）

a baba_a_ 1

a babaa_a_ 1

ab abaa_ab_ 2

aba baa_aba_ 3

abab aa_abab_ 4

ababa a_ababa_ 5

ababaa ababaa 6

最后我们得到一组数值：0 0 1 2 3 1 1 2 3 4 5 6

在这组数开头添加 -1，并删去最后一个数值，数组变为： -1 0 0 1 2 3 1 1 2 3 1 1 2 3 4 5

所有值+1，变为：0 1 1 2 3 4 2 2 3 4 2 2 3 4 5 6，这就是我们需要的 next 数组

需要注意的是，不同的题目next[0]可能为-1，所以 -1 0 0 1 2 3 1 1 2 3 1 1 2 3 4 5 同样有可能作为 next 数组，但是这两种一定不会同时出现。

题目图片：

B. kmp算法中的next到底是什么意思啊

next[j]表代表j之前的字符串的真前缀和真后缀最大匹配长度，它的构成和kmp算法思想一致，只需要置next[0]=-1，再逐次推出next[j]的值

C. 模式匹配KMP算法里面next里保存的值有什么用

next数组存储的数据是用来当模式串与主串不匹配的时候要模式串回退到第几个字符与主串再重新匹配，我们知道KMP算法的主串是不回朔的，当不匹配的时候我们不是退回到开始位置重新匹配，而是利用已经匹配的结果将模式串回朔到下一个位置，这个位置比开始位置更近一步;
简单的说就是next[ j ]的值保存的是当模式串中第 j 个字符与主串第 i 个字符不匹配时候，模式串中的哪个字符 重新与主串第 i 个再匹配，这样总的字符比较次数比从开始位置比较的次数就少了。