代码随想录算法训练营第九天

本文主要是介绍代码随想录算法训练营第九天 | KMP更精良总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

字符串问题：寻找文本串S中是否存在模式串P

暴力法

时间复杂度O(n x m)
第1轮：指针i扫描文本串S、指针j扫描模式串P，同时从索引0开始向右扫描对比。直到S[i] != P[j]，如下图过程(2)。
在这里插入图片描述
第2轮：i回到索引1、j仍回到索引0，如下图过程(3)，同时开始向右扫描对比。若遇到S[i] != P[j]，i回到索引2、j仍回到索引0。
重复若干轮，直到扫描完整个P，都保持S[i] == P[j]，如下图过程(4)，说明文本串S中存在模式串P。
在这里插入图片描述

KMP法

指针i扫描文本串S、指针j扫描模式串P，同时从索引0开始向右扫描对比。直到索引5，此时S[i] != P[j]，如下图过程(1)。

此时，希望通过前缀表next[j-1]找到字符串P[0 – j-1]中的最大相等前后缀：

！！next[j-1] 的定义：表示在数组P[0 – j-1]中存在的最长相等前后缀的长度，假设next[j-1] = t，那么P[0 – t-1] == P[j-t – j-1]。
！！这么做的目的：若能在P[0 – j-1]中找到最长相等前后缀(假设前缀长度=后缀长度=next[j-1]=t)，此时P[0 – t-1] == P[j-t – j-1] == S[i-t – i-1]，那么i就可以从索引5、j从索引t开始继续扫描，如下图过程(2)；若未能找到最长相等前后缀，那么i从索引5、j从索引0继续扫描。

求next数组

先看代码理解过程，不懂的继续看下面讲解。代码过程如下，

假设模式串P=“abxabcabxabx”

void getNext(int* next, const string& P) {	//模式串P/*j为前缀后一位置(如上面P中的字符c位置)，前缀为P[0 -- j-1]="abxab"i为后缀后一位置(如上面P中的最后一个字符x位置)，后缀为P[i-j -- i-1]="abxab"前后缀长度均为j，j在while循环中会变*/int j = 0;	//j为前缀后一位置，前缀从模式串首字符开始next[0] = 0;	//0的位置只能回退到0/*指针i遍历模式串P*/for(int i = 1; i < P.size(); i++) {	//i为后缀后一位置，因为后缀不包含首字母，所以从1开始/*前后缀后一位置不相同：j要向前回退，看前一位的前缀表的数值，就是要回退的下标，因为要找前面字符串的最长相等前后缀长度*//*j要一直回退，直到前后缀后一位置一致，即P[i]==P[j]，此时P[i-1]==P[j-1]、P[i-2]==P[j-2]、...、P[0]==P[j-i]*/while (j > 0 && P[i] != P[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置。如果一直回退，只能退到next[0]，故上面写j>0。}/*前后缀后一位置相同的情况*/if (P[i] == P[j]) { j++;   			}/*更新next数组的值*/next[i] = j;}
}

求next数组就是在用KMP，把P[0 – j]看成模式串、P[1 – i]看成文本串。每次求next[i]，可看作模式串与文本串的一次匹配，在该过程中可用之前所求的next。①文本串一直是每次for循环+1，不会回退。②模式串有时可通过next数组的功能，跳过前几个字符进行比较。

在匹配过程中（即判断P[j]和P[i]是否相等，即while循环）：无论P[j]是否等于P[i]，P[0 – j-1]始终等于P[i-j – i-1]。但j的大小并非始终不变的，最开始j=next[i-1]，即字符串P[0 – i-1]的最长相等前后缀长度；若不匹配则进入while循环，此时j=next[j-1]；若仍不匹配，则继续递归，继续j=next[j-1]。

若不匹配即P[j] != P[i]，j就一直往回退，退到j=0或匹配P[j] == P[i] 为止。 回退过程属于递归过程，当不匹配回退一步时，此时j=next[j]，继续匹配。若最终未匹配，那么j = 0，即next[i] = j = 0。
若匹配即P[j] == P[i]，由于前提条件P[0 – j-1] == P[i-j – i-1]，可得P[0 – j] == P[i-j – i]，那么字符串P[0 – i]的最长相等前后缀长度next[i] = j - 0 = i - (i - j) = j。

举例：模式串P=“abxabcabxabx”
当i=11、j=5时，P[j]=‘c’，P[i]=‘x’，匹配失败，虽然之前已经匹配成功abxab。此时，通过j=next[j-1]=2，使P[j]=‘x’=P[i]，匹配成功。

整体代码

！！！在两份代码中，i扫描文本串，j扫描模式串。

/*获取next数组*/
void getNext(int* next, const string& P) {	//模式串Pint j = 0;	next[0] = 0;for(int i = 1; i < P.size(); i++) {	//！！后缀，文本串/*前后缀后一位置不相同：j要向前回退，看前一位的前缀表的数值，就是要回退的下标*/while (j > 0 && P[i] != P[j]) { //！！前缀，模式串j = next[j - 1]; }/*前后缀后一位置相同的情况*/if (P[i] == P[j]) { j++;   			}/*更新next数组的值*/next[i] = j;}
}

/*文本串S中是否存在模式串P*/
int strStr(string S, string P) {	//文本串S、模式串P/*构建前缀表即next数组*/int next[P.size()];getNext(next, P);//指针i遍历文本串S，指针j遍历模式串Pint j = 0;for (int i = 0; i < S.size(); i++) {// 文本串/*当S[i]!=P[j]时，j要不断回退到下标为【前一个字符的前缀表的数值】的位置，直到S[i]==P[j]*/while(j > 0 && S[i] != P[j]) {	// 模式串j = next[j - 1];			}//若S[i]==P[j]，两个指针同时右移if (S[i] == P[j]) {		j++;}// 当指针j遍历完模式串P，即在文本串S中找到第一个与模式串P相等的字符串，此时i指向该字符串最后一个字符的后一位置if (j == P.size() ) {	return (i - P.size() + 1);	//返回该字符串的首字符位置}}return -1;	// 若文本串S中不存在模式串P，则返回-1
}