哈尔滨网站域名备案,tomcat加jsp做网站,html 网站源码 卖手机,做标书需要用到哪些网站查资料目录 1.什么是KMP2.什么是next数组3.什么是前缀表#xff08;1#xff09;前后缀含义#xff08;2#xff09;最长公共前后缀#xff08;3#xff09;前缀表的必要性 4.计算前缀表5.前缀表与next数组#xff08;1#xff09;使用next数组来匹配 6.构造next数组#xf… 目录 1.什么是KMP2.什么是next数组3.什么是前缀表1前后缀含义2最长公共前后缀3前缀表的必要性 4.计算前缀表5.前缀表与next数组1使用next数组来匹配 6.构造next数组1初始化2处理前后缀不相同的情况3处理前后缀相同的情况4.前缀表不减一C实现 7.使用next数组来做匹配1前缀表统一减一2不减一的整体实现 1.什么是KMP
说到KMP先说一下KMP这个名字是怎么来的为什么叫做KMP呢。 因为是由这三位学者发明的KnuthMorris和Pratt所以取了三位学者名字的首字母。所以叫做KMP。
KMPKnuth-Morris-Pratt算法是一种字符串匹配算法用于在一个主文本字符串中查找一个模式字符串的出现位置。它的核心思想是避免在匹配过程中反复回溯主文本中的位置从而提高匹配效率。
2.什么是next数组
next数组也称为部分匹配表Partial Match Table是KMP算法中的一种预处理技术用于存储模式字符串中每个位置的最长匹配前缀子串的结尾位置。
具体来说next数组的每个元素代表着模式字符串中对应位置的最长匹配前缀子串的结尾位置。通过构建next数组我们可以在匹配过程中根据当前不匹配字符的位置快速确定模式字符串的指针移动的位置从而实现高效的字符串匹配。
3.什么是前缀表
1.在字符串匹配算法中前缀表Prefix Table也被称为部分匹配表Partial Match Table或next数组。它是用于KMP算法中的核心数据结构之一用于存储模式字符串中每个位置的最长匹配前缀子串的结尾位置。
2.前缀表是用来回退的它记录了模式串与主串(文本串)不匹配的时候模式串应该从哪里开始重新匹配。
为了清楚地了解前缀表的来历我们来举一个例子
要在文本串aabaabaafa 中查找是否出现过一个模式串aabaaf 。 可以看出文本串中第六个字符b 和 模式串的第六个字符f不匹配了。如果暴力匹配发现不匹配此时就要从头匹配了。
但如果使用前缀表就不会从头匹配而是从上次已经匹配的内容开始匹配找到了模式串中第三个字符b继续开始匹配。
此时就要问了前缀表是如何记录的呢
首先要知道前缀表的任务是当前位置匹配失败找到之前已经匹配上的位置再重新匹配此也意味着在某个字符失配时前缀表会告诉你下一步匹配中模式串应该跳到哪个位置。 那么什么是前缀表记录下标i之前包括i的字符串中有多大长度的相同前缀后缀。
在上述例子中前缀和后缀就分别为模式串中b前后的aa
1前后缀含义
前缀不包含最后一个字符的所有以第一个字符开头的连续子串。 后缀不包含第一个字符的所有以最后一个字符结尾的连续子串。
2最长公共前后缀
最长公共前后缀就是在字符串某个位置前面的子串和后面的子串中相同的最长长度。例如对于字符串 “abcabc”最长公共前后缀的长度为3因为 “abc” 既是最长的前缀也是最长的后缀。
3前缀表的必要性
刚刚匹配的过程在下标5的地方遇到不匹配模式串是指向f如图 然后就找到了下标2指向b继续匹配如图 能告诉我们上次匹配的位置并跳过去
下标5之前这部分的字符串也就是字符串aabaa的最长相等的前缀和后缀字符串是子字符串aa 因为找到了最长相等的前缀和后缀匹配失败的位置是后缀子串的后面那么我们找到与其相同的前缀的后面重新匹配就可以了。
4.计算前缀表
如图 长度为前1个字符的子串a最长相同前后缀的长度为0。 长度为前2个字符的子串aa最长相同前后缀的长度为1。 长度为前3个字符的子串aab最长相同前后缀的长度为0。
以此类推长度为前4个字符的子串aaba最长相同前后缀的长度为1。 长度为前5个字符的子串aabaa最长相同前后缀的长度为2。 长度为前6个字符的子串aabaaf最长相同前后缀的长度为0。 下标i之前包括i的字符串中有多大长度的相同前缀后缀。
再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示 找到的不匹配的位置 那么此时我们要看它的前一个字符的前缀表的数值是多少。
为什么要前一个字符的前缀表的数值呢因为要找前面字符串的最长相同的前缀和后缀。
所以要看前一位的 前缀表的数值。
前一个字符的前缀表的数值是2 所以把下标移动到下标2的位置继续比配。 可以再反复看一下上面的动画。
最后就在文本串中找到了和模式串匹配的子串了。
5.前缀表与next数组
很多KMP算法的时间都是使用next数组来做回退操作那么next数组与前缀表有什么关系呢
next数组就可以是前缀表但是很多实现都是把前缀表统一减一右移一位初始位置为-1之后作为next数组。
为什么这么做呢其实也是很多文章视频没有解释清楚的地方。
其实这并不涉及到KMP的原理而是具体实现next数组既可以就是前缀表也可以是前缀表统一减一右移一位初始位置为-1。
1使用next数组来匹配
以下我们以前缀表统一减一之后的next数组来做演示。
有了next数组就可以根据next数组来 匹配文本串s和模式串t了。
注意next数组是新前缀表旧前缀表统一减一了。
匹配过程动画如下 两种情况 1.总体往后移到哪一位不匹配就直接找那一位的下标 2.如果在其基础上减去一则是找他前一位的下标1即可
6.构造next数组
我们定义一个函数getNext来构建next数组函数参数为指向next数组的指针和一个字符串。 代码如下
void getNext(int* next, const string s)构造next数组其实就是计算模式串s前缀表的过程。 主要有如下三步
1初始化
定义两个指针i和jj指向前缀末尾位置i指向后缀末尾位置。 然后还要对next数组进行初始化赋值如下
int j -1;
next[0] j;next[i] 表示 i包括i之前最长相等的前后缀长度其实就是j 所以初始化next[0] j 。
2处理前后缀不相同的情况
因为j初始化为-1那么i就从1开始进行s[i] 与 s[j1]的比较。
所以遍历模式串s的循环下标i 要从 1开始代码如下
for (int i 1; i s.size(); i) {next数组的回退操作是为了利用已经计算得到的信息调整模式字符串的指针位置以避免不必要的字符比较提高KMP算法的匹配效率。
while (j 0 s[i] ! s[j 1]) { // 前后缀不相同了j next[j]; // 向前回退
}3处理前后缀相同的情况
如果 s[i] 与 s[j 1] 相同那么就同时向后移动i 和j 说明找到了相同的前后缀同时还要将j前缀的长度赋给next[i], 因为next[i]要记录相同前后缀的长度。
if (s[i] s[j 1]) { // 找到相同的前后缀j;
}
next[i] j;最后整体构建next数组的函数代码如下
void getNext(int* next, const string s){int j -1;next[0] j;for(int i 1; i s.size(); i) { // 注意i从1开始while (j 0 s[i] ! s[j 1]) { // 前后缀不相同了j next[j]; // 向前回退}if (s[i] s[j 1]) { // 找到相同的前后缀j;}next[i] j; // 将j前缀的长度赋给next[i]}
}如下为next数组的流程图
4.前缀表不减一C实现 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要保证大于0因为下面有取j-1作为数组下标的操作j next[j - 1]; // 注意这里是要找前一位的对应的回退位置了}if (s[i] s[j]) {j;}next[i] j;}}7.使用next数组来做匹配
i就从0开始遍历文本串代码如下
for (int i 0; i s.size(); i) 接下来就是 s[i] 与 t[j 1] 因为j从-1开始的 进行比较。
如果 s[i] 与 t[j 1] 不相同j就要从next数组里寻找下一个匹配的位置。
代码如下
while(j 0 s[i] ! t[j 1]) {j next[j];
}如果 s[i] 与 t[j 1] 相同那么i 和 j 同时向后移动 代码如下
if (s[i] t[j 1]) {j; // i的增加在for循环里
}本题要在文本串字符串中找出模式串出现的第一个位置 (从0开始)所以返回当前在文本串匹配模式串的位置i 减去 模式串的长度就是文本串字符串中出现模式串的第一个位置。
if (j (t.size() - 1) ) {return (i - t.size() 1);
}那么使用next数组用模式串匹配文本串的整体代码如下
int j -1; // 因为next数组里记录的起始位置为-1
for (int i 0; i s.size(); i) { // 注意i就从0开始while(j 0 s[i] ! t[j 1]) { // 不匹配j next[j]; // j 寻找之前匹配的位置}if (s[i] t[j 1]) { // 匹配j和i同时向后移动j; // i的增加在for循环里}if (j (t.size() - 1) ) { // 文本串s里出现了模式串treturn (i - t.size() 1);}
}1前缀表统一减一
class Solution {
public:void getNext(int* next, const string s) {int j -1;next[0] j;for(int i 1; i s.size(); i) { // 注意i从1开始while (j 0 s[i] ! s[j 1]) { // 前后缀不相同了j next[j]; // 向前回退}if (s[i] s[j 1]) { // 找到相同的前后缀j;}next[i] j; // 将j前缀的长度赋给next[i]}}int strStr(string haystack, string needle) {if (needle.size() 0) {return 0;}int next[needle.size()];getNext(next, needle);int j -1; // // 因为next数组里记录的起始位置为-1for (int i 0; i haystack.size(); i) { // 注意i就从0开始while(j 0 haystack[i] ! needle[j 1]) { // 不匹配j next[j]; // j 寻找之前匹配的位置}if (haystack[i] needle[j 1]) { // 匹配j和i同时向后移动j; // i的增加在for循环里}if (j (needle.size() - 1) ) { // 文本串s里出现了模式串treturn (i - needle.size() 1);}}return -1;}
};2不减一的整体实现
class Solution {
public: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;}}int strStr(string haystack, string needle) {if (needle.size() 0) {return 0;}int next[needle.size()];getNext(next, needle);int j 0;for (int i 0; i haystack.size(); i) {while(j 0 haystack[i] ! needle[j]) {j next[j - 1];}if (haystack[i] needle[j]) {j;}if (j needle.size() ) {return (i - needle.size() 1);}}return -1;}
};
