由于高中参加信竟时总是划水摆烂，加上学习的时候总是容易钻牛角尖，导致各种算法的学习并没有理想中的顺利，最后只取得了一个参与奖（只能算是参与奖，因为没有实质上的用处）。今天在机缘巧合下，又学习了一下KMP算法。KMP算法是一个计算字符串B在字符串A中的位置的算法（具体介绍详见网络）。KMP算法通过预先生成一个next数组。对于作为搜索目标的字符串B，该数组中第i个元素next[i]表示：当B[i]!=A[j]时（即碰到不匹配的情况），i应当回退到的位置为next[i]，而不需要从B[0]开始搜索，降低时间复杂度（同时A字符串也不需要再从A[0]开始，而是继续往下走）。最终达到O(m+n)的时间复杂度。通过网络搜索，搜到一篇文章：https://zhuanlan.zhihu.com/p/83334559作者提出，KMP可以以DP的思想来理解，于是我豁然开朗（实际上在脑袋里头脑风暴），突然（实则不然）理解了经典的计算next数组的方式。但是经典计算方式在循环中需要两个自变量，我又想着能不能只用1个（经典俺寻思，但是可能已经有人想过了，但是我没看到）。
错误尝试
一开始，我想着构建这样的next数组：
注意到next数组中就储存着用于比较的i的index，因此我想着通过比较B[i]和B[next[i-1]]的字符是否相等，如果相等的话，将next[i]赋值为next[i-1]+1（是不是联想到DP的状态转移方程）；否则赋值为0。同时将next[0]初始化为0。
但是，经过验算可以发现，在i=3时，next[i]会被赋值成1，也就是说，如果使用这个next数组来做KMP的话，会导致错误的跳转。
纠正
于是我们将其作简单调整，将next[0]初始化为-1，我们定义next[i]==-1表示回到B的开头，与next[i]==0相同。
于是我们有：
当B[i]==B[next[i-1]+1]时，
next[i]=next[i-1]+1；
否则，
next[i]=-1；
为了验证猜想，我们在上图中excel中c3:j3设置公式：
=IF(OFFSET(B2,0,OFFSET(INDIRECT(ADDRESS(ROW(),COLUMN())),0,-1)+1)=OFFSET(INDIRECT(ADDRESS(ROW(),COLUMN())),-1,0),OFFSET(INDIRECT(ADDRESS(ROW(),COLUMN())),0,-1)+1,-1)
这样，我们只要改变第二行中的字符，next数组也会自动更新。
接下来，就可以用代码完成KMP了。
#include<stdio.h>#include<string.h>//输入template字符串的地址，next数组地址，next[i]表示当第i位匹配失败时，应该跳转到的位置 voidgetNext(char* template,int *next){int len=strlen(template); next[0]=-1;for(int i=1;i<len;i++){if(template[i]==template[next[i-1]+1]){ next[i]=next[i-1]+1; }else{ next[i]=-1; } }} intdoKMPSearch(char*S,char*template,int*next){int lenS=strlen(S),lenT=strlen(template);int i=0,j=0;while(i<lenS&&j<lenT){if(j<0||S[i]==template[j]){ i++,j++; }else{ j=next[j]; } }if(j==lenT)return i-j;return -1;}intmain(){char str[200];char t[10];int next[10];scanf("%s",&str);scanf("%s",&t);getNext(t,next);int index=doKMPSearch(str,t,next);printf("“%s”在“%s”中的位置为：%d",str,t,index);return 0;}
