从零开始的数据结构学习日记（九）——1.9KMP算法_串匹配的kmp算法伪代码

1.1KMP算法

先给出KMP算法伪代码：
1.在目标串T和模式串P中分别设置比较的起始下标i和j
2.当(i<n&&j<m)时，重复以下操作，直到目标串T或者模式串P的字符都比较完毕
——2.1如果T[i]等于p[i]，则继续比较T和P的下一对字符
——2.2否则将模式串P的下标j回溯到P中的next[j]位置，即j=next[j]
——2.3如果j=-1，则将下标i和j分别加1，准备下一趟比较
3.如果P中所有的字符均比较完成，则匹配成功，返回最后一趟匹配开始位置；否则匹配失败返回0
计算next数组的算法伪代码如下：
1.赋初值j=0；k=-1；next[0]=-1
2.当j<length§时，重复以下操作，直到模式串P中所有字符均处理完毕
——2.1如果k=-1或者pj等于pk，分别将j和k加1，然后将k赋给next[j]
——2.2否则将next[k]赋给k
3.返回next数组的值
浏览csdn发现如下好办法：

下面介绍一到北邮2016年考研真题
1 2 3 4 5 6 7 8
a b a a b c a c
0 1 1 2 2 3 1 2
这是一个考试常见的字符串，是如何计算的那？
第n位：next[n]的值来自于第n-1位的字符，通过跟第next[n-1]位字符比较，如果相同next[n]=next[n-1],如果不相同，就跟第next[next[n-1]]位的字符比较，就这样迭代直到相同的时候，加上1，如果实在没有，就为1.
这一段话可能很难理解，逐位分析。
让我们从依次来看：
第3位：第2位和第1位比较，不相同 所以为1
第4位：第3位和第1位比较，相同，所以为2
第5位：第4位和第2位比较，不相同，和第1位比较，相同，所以为2
第6位：第5位和第2位比较， 相同，所以为3
第7位：第6位和第3位比较，不同，和第1位比较，不同，所以为1
第8位：第7位和第1位比较，相同，所以为2.
这就是next数组的手动计算方法。
————————————————
版权声明：本文为CSDN博主「qq_37747664」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37747664/article/details/82734448

如果这个方法还是不能理解，笔者这里有一个自用的玄学 办法描述如下：
我们观察要计算next数组的字符串的头和尾，比如所引文章中的“abaabcac”，前两位为0和1，第三位因为前两位不相同为1，第四位的数组因为“aba”子串的前缀和后缀有一个相同的字母a所以为2，第五位因为子串“abaa”前缀后缀中有一个a相同所以为2，第六位因为子串“abaab”前后缀中有ab相同所以为3，以此类推。