求KMP的算法

求KMP的算法### 求next数组方法：

首先求每个子串的最长前后缀

1、next 数组的定义

next 数组（前缀表）是在 KMP 算法中使用到的，用于匹配模式串相同前后缀长度

它可以减少匹配次数，其原理是将模式串中每个子串的相同前后缀长度记录下来，当在文本串中匹配失败时，就根据前缀表——即 next 数组——找到模式串中匹配失败前一个字符的位置所对应的前缀尾字符，将模式串的指针移动到该字符

过程说明：

 下标从0开始  0 1 2 3 4 5 6 7 8  文本串  a a b a a b a a f  模式串  a a b a a f  next 数组  0 1 0 1 2 0  右移补-1的next 数组  − 1 0 1 0 1 2  模式串  a a b a a f  下标从1开始  1 2 3 4 5 6 7 8 9  右移补-1的基础上整体加1的next 数组  0 1 2 1 2 3 \begin{array}{|r|l|l|l|l|l|l|l|l|l|l|} \hline \text { 下标从0开始 } & \mathbf{0} & \mathbf{1} & \mathbf{2} & \mathbf{3} & \mathbf{4} & \mathbf{5} & \mathbf{6} & \mathbf{7} & \mathbf{8} \\ \hline \text { 文本串 } & \mathrm{a} & \mathrm{a} & \mathrm{b} & \mathrm{a} & \mathrm{a} & \mathrm{b} & \mathrm{a} & \mathrm{a} & \mathrm{f} \\ \hline \text { 模式串 } & \mathrm{a} & \mathrm{a} & \mathrm{b} & \mathrm{a} & \mathrm{a} & \mathrm{f} & & & \\ \hline \text { next 数组 } & 0 & 1 & 0 & 1 & 2 & 0 & & & \\ \hline \text { 右移补-1的next 数组 } & -1 & 0 & 1 & 0 & 1 & 2 & & & & \\ \hline \text { 模式串 } & & & \mathrm{a} & \mathrm{a} & \mathrm{b} & \mathrm{a} & \mathrm{a} & \mathrm{f} & & & \\ \hline \text { 下标从1开始 } & \mathbf{1} & \mathbf{2} & \mathbf{3} & \mathbf{4} & \mathbf{5} & \mathbf{6} & \mathbf{7} & \mathbf{8} & \mathbf{9} \\ \hline \text { 右移补-1的基础上整体加1的next 数组 } & 0 & 1 & 2 & 1 & 2 & 3 & & & & \\ \hline \end{array}  下标从0开始  文本串  模式串  next 数组  右移补-1的next 数组  模式串  下标从1开始  右移补-1的基础上整体加1的next 数组 ​0aa0−110​1aa1021​2bb01a32​3aa10a41​4aa21b52​5bf02a63​6aa7​7af8​8f9​​​​

求next数组方法：

1. 求每个字串对最长前后缀
   1. a的最长前后缀为0
   2. aa的最长前后缀为1
   3. aab的最长前后缀为0
   4. aaba的最长前后缀为1
   5. aabaa的最长前后缀为2
   6. aabaaf的最长前后缀为0
   7. 求得最长前后缀数组为[0,1,0,1,2,0]
2. 右移补-1得到next数组，目的就是让失配点的下标直接指向字符长为5的最长前后缀的下一个位置开始匹配（最长前后缀的位置一定会失配因此跳过）。
3. 如果数组下标从1开始就，整体加1。
4. 【总结】：第一位-1，求1到n位子串前后缀长度得到数组，将得到的数组整体加1。