苏州微网站开发,网站制作的主要技术,哪个公司的网站做的好,湖南有线郴州网络有限公司1.何为KMP算法 KMP算法是由Knuth、Morris和Pratt三位学者发明的#xff0c;所以取了三位学者名字的首字母#xff0c;叫作KMP算法。
2.KMP的用处 KMP主要用于字符串匹配的问题#xff0c;主要思想是当出现字符串不匹配时#xff0c;我们可以知道一部分之前已经匹配过的的文…1.何为KMP算法 KMP算法是由Knuth、Morris和Pratt三位学者发明的所以取了三位学者名字的首字母叫作KMP算法。
2.KMP的用处 KMP主要用于字符串匹配的问题主要思想是当出现字符串不匹配时我们可以知道一部分之前已经匹配过的的文本内容利用这些信息从而避免从头再开始匹配。 但是如何才能知道之前已经匹配过的内容呢这是KMP算法的核心也是KMP算法里面的next数组的用处。
3.最长相等前后缀 一个字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续字串 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串 前缀表也就是next数组要求的是最长相等前后缀的长度例如a的最长相等前后缀为0aaa得到最长相等前后缀为2aaba的最长相等前后缀为1。
4.next数组(前缀表) KMP的核心就是next数组当模板串和主串不匹配时next数组是用来让模板串知道应该从哪里再开始匹配。 next数组记录下标i之前(包括i)的字符串中有多大长度的相等前后缀。 这里借用了代码随想录的图片 比如我们要在文本串aabaabaafa中寻找模板串aabaaf在b和f之前发现匹配不了如果用暴力算法就要从头开始匹配文本串和模板串都需要进行回退时间复杂度是很高的但如果我们使用KMP算法next数组记录了f之前有多大长度的相等前后缀也就是我们知道了之前匹配过的内容就会从上次已经匹配的内容开始匹配这里为什么能这样呢我是这样理解的 文本串: aabaabaafa 用i遍历 模板串aabaaf 用j遍历 在b和f时不相同了这时候我们不想再匹配我们已经匹配过的也就是说我们不想i回退而是一直向前走那我们就要j进行回退回退到什么位置呢前面已经匹配到了说明已经匹配过的文本串aabaa中含有模板串一部分内容又因为前后缀有相等的部分。所以我们回退到前后缀相等的前缀位置因为和文本串是相同的所以aabaa的后缀aa和文本串的aabaa的后缀aa是相等的又有aabaa的前缀aa和后缀aa是相等前后缀所以前缀aa和文本串aabaa的后缀aa相等我们回退到aabaa的b即可避免再次匹配aabaa的前缀aa这样也可以保证模板串aabaa的前缀aa是已经匹配过的。 f之前这部分的字符串也就是字符串aabaa的最长相等前后缀是aa 因为找到了最长相等的前后缀匹配失败的位置是后缀的后面那么我们找到与其相同的前缀的后面重新匹配就可以了。
5.如何计算next数组 例如a a b a a f下标0 1 2 3 4 5next 0 1 0 1 2 0 当下标为0时长度为前1个字符的字串a最长相等前后缀的长度为0 当下标为1时长度为前2个字符的字串aa最长相等前后缀的长度为1 依次类比可以得到next数组也就是前缀表 可以看出模板串和next数组对应位置的数字表示的是下标i之前(包括i)的字符串中有多大长度的最长相等前后缀。 当我们找到不匹配的位置时就要看它前一个字符的next数组的值是多少因为我们要找前面字符串的最长相等前后缀所以要看前一位的next数组的值前一个字符的next数组值为2所以我们把下标j移动到2的位置继续匹配这样就可以匹配到了。
6.next数组实现 主要是处理前后缀相等和不相等的情况我们首先定义一个getNext函数来构造next数组参数为指向next数组的指针和一个字符串
void getNext(int* next,string s) 接着我们对其进行初始化定义两个指针i和jj指向前缀末尾i指向后缀末尾对next数组进行初始化赋值
int j0;
next[0]j; next[i]表示i(包括i)之前最长相等的前后缀长度就是j所以初始化next[0]j
6.1前后缀不相同 j0所以我们从i1开始遍历文本串就像这样
for(int i0;is.size();i) j首先要保证是大于0的因为下面j要回退然后就是s[i]和s[j]的比较如果s[i]和s[j]不相同j就要找前一位对应的回退位置因为这里j之前的前缀已经和i的后缀不相等了所以我们就要j进行回退。
while(j0s[i]!s[j])
{jnext[j-1];
} 6.2前后缀相同 如果是s[i]和s[j]相同这时候只要同时移动i和j这时候找到了相同的前后缀我们要把j的值赋值给next[i]因为next[i]记录相同前后缀的长度
if(s[i]s[j])
{j;
}
next[i]j; 完整代码如下
void getNext(int* next, const string s)
{int j 0;next[0] 0;for(int i 1; i s.size(); i) {while (j 0 s[i] ! s[j]){ j next[j - 1]; }if (s[i] s[j]){j;}next[i] j;}
}7.例题 void getNext(int* next,const string s){int j0;next[0]0;for(int i1;is.size();i){while(j0s[i]!s[j]){jnext[j-1];}if(s[i]s[j]){j;}next[i]j;}}int strStr(string haystack,string needle){if(needle.size()0){return 0;}int next[needle.size()];getNext(next,needle);int j0;for(int i0;ihaystack.size();i){while(j0haystack[i]!needle[j]){jnext[j-1];}if(haystack[i]needle[j]){j;}if(jneedle.size()){return (i-needle.size()1) ;}}return -1;} 这道题很明显是字符串匹配的问题所以我们使用KMP算法首先是next数组的构建这是模板直接写就行然后就是模板串和文本串的匹配如果不相同那j就回退到next[j-1]如果相同j就直接向后移动即可当j和模板串的长度相等时此时i一定是大于等于模板串的长度的因为i之前的文本串是包含模板串的所以我们用i-模板串的长度1就是第一个匹配项的下标了。
