大家好，如果您还对深入探讨数据结构（第十一讲）不太了解，没有关系，今天就由本站为大家分享深入探讨数据结构（第十一讲）的知识，包括的问题都会给大家分析到，还望可以解决大家的问题，下面我们就开始吧！
思路
首先，我们看一个例子，主字符串abcdefgab 和模式字符串abcdex。在第一轮比较中，KMP算法和BF算法从第一个字母开始匹配。
abcdefgab
如果第一轮abcdex 匹配成功，则第二轮开始比较第二个字符，以此类推。
kmp01.png 如果模式串中没有后续字符与第一个字母b匹配，那么我们可以忽略接下来的四次比较，直接将模式串移动到第六个字母开始匹配，即可以忽略。之所以保留步骤，是因为我们知道T[0]T[5]，但无法确定T[1]S[5]。
如果有重复的字符会怎样？让我们看另一个例子。主字符串是abcabcabc，模式字符串是abcabx。对比如下：
kmp02.png 由于模式串中的前五个字符abcab中，前两个字符ab和后两个字符ab相等，因此上述两个步骤也可以省略。
对比这两个例子，我们发现去掉这些不必要的比较后，i值就不再回溯了，所以我们需要考虑j的变化。而且我们还可以发现，j的变化实际上是由模式串中是否存在相等的前缀和后缀决定的，与主串无关。这时候就引入了一个重要的概念，下一个数组。
next数组
接下来的数组是一个一维整数数组，它是KMP算法的核心。只要得到这个数组，我们就可以确定每次遍历模式串时如何回溯。那么如何导出这个数组呢？
因为next 数组用于模式字符串，所以next 的长度就是模式字符串的长度。接下来数组又分为两种情况。一是字符串的第一个位置存储的是字符串的长度而不是内容。第二个是第一个位置是字符串的内容。需要注意的是，next数组对应的是当前字符之前的子串中后缀的匹配。
非标准串
下表中字符串的内容从1开始，即第一个位置存储字符串的长度。
我们可以得到如下定义：
Next.png 需要注意的是，下一个数组默认从1开始。我们来推导下一个数组：
abcdex 当j==1时，默认next[1]=0；当j==2时，j从1到j-1只有一个字符a，next[2]=1；当j==3时，j从1到j-1只有一个字符ab，且a和b不相等，next[3]=1；同样，next[j]=011111abcabx 当j==1 时，默认next[1]=0 ；当j==2时，j从1到j-1只有一个字符a，next[2]=1；当j==3时，同上，next[3]=1；当j==4时，同上，next[4]=1；当j==5时，子串为abca。此时前缀a等于后缀a，满足第二个条件，即P1=P4。由P1=Pj-k+1 得出k=2，即next[5]=2；当j==6时，子串为abcab。此时前缀ab等于后缀ab，满足第二个条件，即P1P2=P4P5，由P1Pk-1=Pj-k+1Pj-1可以得出k=3，即下一个[6]=3；也就是说，next[j]=011123ababaaaba。当j==1时，默认next[1]=0；当j==2 时，j 从1 到j-1 只有一个字符a，next[2]=1；当j==3时，同上，next[3]=1；当j==4 时，同上，子串为aba ，此时前缀a 等于后缀a，满足第二个条件，即P1=P3。由P1=Pj-k+1，可得k=2，即next[4]=2；当j==5 时，子串为abab。此时前缀ab等于后缀ab，满足第二个条件，即P1P2=P3P4。由P1Pk-1=Pj-k+1Pj-1，可得k=3，即next[5]=3；当j==6时，子串是ababa。此时前缀aba等于后缀aba，满足第二个条件，即P1P2P3=P3P4P5。可以得出k=4，即next[6]=4；当j==7时，子串是ababaa。此时前缀a等于后缀a，满足第二个条件，即P1=P6。可以得出k=2，即next[7]=2；当j==8时，子串为ababaaa。此时前缀a等于后缀a，满足第二个条件，即P1=P7。可以得出k=2，即next[8]=2；当j==9 时，子串为ababaaab。此时前缀av等于后缀av，满足第二个条件，即P1P2=P7P8。可以得到k=3，即next[8]=3；也就是说，next[j]=011234223aaaaaaaab。 Out next[j]=012345678 那么如何用代码实现next数组呢？如果我们遍历模式串找到每个子串，然后比较该子串对应的后缀和后缀元素，确定数量相等，这样查找下一个数组就会比较麻烦。通过指针回溯的方法比较简单。我们来看看如何通过指针回溯找到下一个数组：
由上式可知，next[1]=0；使用指针i 遍历模式串，使用指针j 回溯。当T[i]==T[j] 时，通过i++、j++，可以得到next 字符对应的下一个数组值，即next[i]=j。当T[i] !=T[j]时，j需要追溯到合理的位置。请注意，这是很重要的一点。什么是合理的位置？比如aabaaxaaa，当我们遍历到第七个a位置时，即子串为aabaax，此时b和x不相等（j=3，i=6），没有匹配的后缀，所以我们需要回溯。因为之前第一个和第二个a以及第四个和第五个a已经匹配成功了，所以我们回到第二个a与x进行比较，即回到j=2的位置。 aabaaxaaa的next数组为012123123，表示j=next[j]=2，当回溯无法匹配时，最终会到达j=next[1]=0，即从头开始匹配，并且根据公式得到next[i]=1。代码实现如下：
//注意字符串T[0]是存储的字符串的长度；真实的字符内容从T[1]开始；
无效getNexts（字符串T，int *下一个）{
整数i=1;
整数j=0;
下一个[1]=0;
而（iT[0]）{
if (j==0 || T[i]==T[j]) {
//当i==0时，表示回溯时没有匹配到，即不存在相等的后缀。
我+=1；
j+=1；
下一个[i]=j;
} 别的{
//如果字符不相同，则回溯j值；
//回溯到上一个比较位置。如果仍然不相同，则继续回溯。
//如果回到j=1时仍然没有值，则说明整个子串中没有对应的后缀元素，则直接将next的值设置为1
j=下一个[j];
}
}
}获得下一个数组，然后我们可以用它来进行模式字符串匹配。匹配过程与BF算法相同。唯一的区别是，当字符不匹配时，不需要回溯主串，而是回溯模式串。
//T[0]和S[0]存储字符串T和字符串S的长度
int KMP(字符串S, 字符串T) {
if (S==NULL || T==NULL || T[0]==0 || S[0]=T[0]) {
返回0；
}
整数i=1;
整数j=1;
int *next=(int *)malloc(sizeof(int) * (T[0] + 1));
getNexts(T, 下一个);
//如果i小于S的长度，j小于T的长度，则继续循环；
而（i=S [0] j=T [0]）{
//如果两个字母相等则继续，j++、i++继续比较
if(j==0 || S[i]==T[j]) {
我+=1；
j+=1；
} 别的{
//如果没有匹配到，则j会回溯到next中对应的位置
j=下一个[j];
}
}
如果（jT[0]）{
返回i - T[0]；
} 别的{
返回-1；
}
从代码中可以看出，KMP算法的时间复杂度为O(m+n)，相比BF算法还是有明显提升。但上述实现仍存在缺陷。例如主字符串S=aaaabcde，模式字符串T=aaaaax，下一个数组为012345，匹配过程如下：
kmp03.png 事实上，当i=5，j=5时可以得到ba，因此步骤的回溯是没有意义的。由于模式串的前几个字符都是相等的，所以我们可以用next[1]的值来替换next[j]的后几个字符，以达到优化的目的。
我们来推导一下新数组nextval的实现：
模式字符串aaaaax 的Next[j]=012345。当j==1时，默认nextval[1]=0；当j==2时，第二个字符为a，next[2]=1，第一个字符为a，相等，nextval[2]=nextval[1]=0；当j==3 时，因为第三个位置的字符是a, next[3]=2，第二个位置的字符是a, equal ，所以nextval[3]=nextval[2]=0；当j==4时，因为第4个位置的字符是a，next[4]=3，所以第3个位置的字符是a，相等，nextval[4]=nextval[3]=0；当j==5时，因为第5个位置的字符是a，所以next[5]=4，而第4个位置的字符是a，相等，所以nextval[5]=nextval[4]=0；当j==6时，因为第6个字符是x，所以next[6]=5，第5个字符是a，不相等，所以nextval[6]=next[6]=5；即，模式字符串abcabx 的nextval[j]=000005 next[j]=011123。当j==1时，默认nextval[1]=0；当j==2时，第二个字符为b，next[2]=1，第1个位置的字符为a，不相等，nextval[2]=next[2]=1；当j==3时，因为第3个位置的字符是c，所以next[3]=1，第1个位置的字符是a，不相等，所以nextval[3]=next[3]=1；当j==4时，因为第4个位置的字符是a，所以next[4]=1，第1个位置的字符是a，相等，nextval[4]=nextval[1]=0；当j==5时，因为第5个位置的字符是b，所以next[5]=2，所以第2个位置的字符是b，等于，nextval[5]=nextval[2]=1；当j==6时，因为第6个位置的字符是x，所以next[6]=3，第3个位置的字符是c，不相等，nextval[6]=next[6]=3；即nextval[j]=011013。优化后的代码如下：
无效getNextvals(字符串T,int *nextval){
整数i=1;
整数j=0;
下一个值[1]=0;
而（iT[0]）{
if (j==0 || T[i]==T[j]) {
我+=1；
j+=1；
如果(T[i] !=T[j]) {
nextval[i]=j;
} 别的{
//如果当前字符和前缀字符相同，则将前缀字符的nextval值赋给当前字符
nextval[i]=nextval[j];
}
} 别的{
j=nextval[j];
}
}
}通过执行代码，我们可以看到示例kmp("abcddddabcabx", "abcabx")在优化前会循环14次，优化后会循环13次，而示例kmp("aaaaabaabaaaaax", "aaaaax")会在优化前循环13次optimization 会循环22次，优化后会循环16次。
标准串
字符串的第一个位置元素是字符串的内容。可以得到如下定义：
这个推导过程与上面相同，这里不再赘述。例如，issip 获取的下一个数组是-10001。
我们看一下代码实现：
无效getNexts(char *T, int *next, int tlen) {
整数i=0;
整数j=-1；
//默认下一个[0]=-1
下一个[0]=-1;
而(i tlen - 1) {
if (j==-1 || T[j]==T[i]) {
j++;
我++；
下一个[i]=j;
} 别的{
j=下一个[j];
}
}
}
int kmp(char *S, char *T) {
int slen=(int)strlen(S);
int tlen=(int)strlen(T);
如果（tlen==0）{
返回0；
}
如果（特伦斯伦）{
返回-1；
}
int *next=(int *)malloc(sizeof(int) * tlen);
getNexts(T, 下一个， tlen);
整数i=0;
整数j=0;
while (i slen j tlen) {
如果（S[i]==T[j]）{
if (j==tlen - 1) {
返回i - tlen + 1；
}
j+=1；
我+=1；
} 别的{
如果（下一个[j]=0）{
j=下一个[j];
} 别的{
//如果模式串的起始位置不相等，则主串需要移动一位，模式串需要追溯到第一个字符位置。
j=0；
我+=1；
}
}
}
返回-1；
【深入探讨数据结构（第十一讲）】相关文章：
2.米颠拜石
3.王羲之临池学书
8.郑板桥轶事十则
用户评论
终于来到第十一篇了！感觉学的数据结构越来越丰富了
有14位网友表示赞同！
希望这篇文章能讲解一些更高级的数据结构
有11位网友表示赞同！
我最喜欢图论，不知道这篇文章会介绍哪些图的相关算法？
有17位网友表示赞同！
数据结构是计算机科学的基础，一定要好好学习!
有11位网友表示赞同！
期待这篇文章能深入浅出地解释复杂的概念
有6位网友表示赞同！
我的代码水平想要提升，数据结构真的太重要了
有16位网友表示赞同！
每次看到新的数据结构都觉得很兴奋！
有15位网友表示赞同！
在面试的时候数据结构也是必考的内容吧
有14位网友表示赞同！
看来这次要好好加强一下数据结构的学习才行
有9位网友表示赞同！
这篇文章能让我更好地理解代码背后的逻辑吗？
有10位网友表示赞同！
希望作者能够结合实际案例进行讲解，更易于理解
有13位网友表示赞同！
看标题就感觉很有深度了！
有17位网友表示赞同！
数据结构也是学计算机科学需要掌握的一项技能
有5位网友表示赞同！
我正在学习一个新项目，这篇文章或许能给我提供一些参考
有6位网友表示赞同！
希望这篇文章讲得简单易懂
有6位网友表示赞同！
我的朋友推荐了这本书，应该很有用！
有14位网友表示赞同！
数据结构是编程的基石，想要成为一名优秀的程序员就需要熟练掌握它
有16位网友表示赞同！
我也想学习数据结构，不知道这篇文章适合初学者吗？
有18位网友表示赞同！
我很期待着阅读这篇文章并加深对数据结构的理解
有19位网友表示赞同！
这篇文章一定能够帮助我在编程方面进步！
有6位网友表示赞同！