德语网站建设注意事项,南通网站推广优化费用,家装网站建设案例,杭州家装设计公司排名榜子串的定位操作通常称作串的模式匹配。你可以理解为在一篇英语文章中查找某个单词是否存在#xff0c;或者说在一个主串中寻找某子串是否存在。朴素的模式匹配算法假设我们要从下面的主串S goodgoogle 中#xff0c;找到T google 这个子串的位置。…子串的定位操作通常称作串的模式匹配。你可以理解为在一篇英语文章中查找某个单词是否存在或者说在一个主串中寻找某子串是否存在。朴素的模式匹配算法假设我们要从下面的主串S goodgoogle 中找到T google 这个子串的位置。利用朴素的模式匹配算法我们通常需要下面的步骤。(1)主串S第一位开始S与T前三个字母匹配成功但S第四个字母是d而T的是g。第一位匹配失败。如下图所示浅绿色方块代表匹配成功红色方块代表匹配失败。(2)主串S从第二位开始主串S首字母是o要匹配的T的首字母是g。匹配失败(3)主串S第三位开始主串S首字母是o要匹配的T首字母是g匹配失败(4)主串S第四位开始主串S首字母是d要匹配的T首字母是g匹配失败(5)主串S第五位开始S与T6个字母全部匹配匹配成功简单来说朴素的模式匹配算法就是对主串的每一位字符作为子串的开头与要匹配的子串进行比较如果匹配不成功则主串需要回溯到与子串开始匹配的位置的下一个位置。当子串与主串有较多的相等的字符时这种算法的效率是极其低下的。例如KMP模式匹配算法如果你忍受不了朴素的模式匹配算法。于是有三位前辈D.E.KnuthJ.H.Morris和V.R.Pratt发表了一个模式匹配算法可以大大避免重复遍历的情况我们把他称之为克努特-莫里斯-普拉特算法简称KMP算法。在去理解KMP算法时你需要知道一个字符串的前缀和后缀是什么下面以字符串 google 为例他的前缀集合{ g, go, goo, goog, googl }。它的后缀集合{ e, le, gle, ogle, oogle }。2.1 KMP算法匹配方式假设我们要在主串S ABBABBABABAAABABAAA 中查找模式串T ABBABAABABAA 中的位置。(1)我们发现主串S和子串T的前5个字符均是匹配的第6个字符是不匹配的。下一步我们肯定不能回溯到主串第二个字符的位置不然就是在重走朴素的模式算法的道路了。我们观察发现1匹配了五个字符中2在模式串的左右两端有两个字符子串他们是完全匹配的。我们称之为最长公共前后缀。(2)移动模式串使得原来模式串的前缀到达模式串的后缀的位置这样的移动可以使得重新开始匹配的位置之前的字符均是匹配的因为公共前后缀AB是匹配的并且原来的5个字符也是匹配的所以将模式串的前缀移动到后缀的位置与主串的后缀是匹配的。这样移动可以省去部分字符的不必要匹配这样移动的正确性我们稍后探讨。(3)我们发现模式串的移动与主串并没有关系因为只是将模式串的前缀移动到了模式串的后缀的位置并且已经匹配的字符与主串肯定是一样的撒。这时我们对一般情况做出分析我们现在已经明白了为什么要移动模式串的前缀到后缀的位置以及这样移动的正确性。(4)现在我们可以继续匹配一下主串理解上述的操作2.2 next数组的手动推导上面的图解以及分析仅是一个形象化的过程我们还得将其转化为计算机能够处理的方式。emm我们假设存储字符串是从下标为1的位置开始的呢下面以具体的例子主串S ABABABAABABAAABABAA模式串T ABABAAABABAA来分析如何转化成计算机能够处理的方式。上面分析过在模式串的移动过程中与主串是没有关系的我们只需要分析模式串即可模式串的任何一个位置都可能与主串发生不匹配我们就是要将不匹配之后模式串由前缀移动到后缀的过程抽象成计算机能处理的形式。我们发现有这样的规律next数组对应的值是最长的公共前后缀加1。模式串剩余的字符就不再画图分析了我们将上面的数组取名为next数组例如我们发现模式串在与主串比较时下标为5的位置发生了不匹配我们只需要查找next[5] 的值值为3就知道下一步是将模式串的3号位与主串的当前位置进行比较。2.3 next数组的代码分析/// summary
/// 求解next数组
/// /summary
/// param names 模式串的首字符地址 /param
/// param namen 模式串的字符个数 /param
/// param namenext next数组的首元素地址 /param
void getNext(char* s, int n, int* next)
{//遍历模式串int i 1;//为next数组赋值int j 0;//第一个字符不匹配将编号赋值为0代表从主串的下一个位置开始比较next[1] 0;while (i n){if (j 0 || s[i] s[j])next[i] j;elsej next[j];}
}现在我们先以一个具体的例子来看代码是否正确哈假设模式串为ababnext[1] 需要一开始就初始化的哈。用i遍历模式串时如果j指向的字符与i指向的字符相等进入if分支说明最长公共前后缀需要增加1为什么是增加1呢因为i一次只能遍历一个字符嘛如果i指向的字符与j指向的字符不相等的话进入else分支令jnext[j]即更新j的位置将新的j指向的字符与i指向的字符进行比较看是否相等不相等继续令jnext[j]直到j指向的字符与i指向的字符相等或者说j为0。为什么j的更新是jnext[j]? 我们下面就来分析原因这下你就能理解求next数组的全部代码啦。2.4 查找子串的完整代码下面是字符串从下标为1开始存储时的查找子串的代码。只是以一个具体的例子实践了一下你只要理解了思路就随便写代码的。这里的代码仅供参考具体代码还需结合题目具体分析/// summary
/// 求解next数组
/// /summary
/// param names 模式串的首字符地址 /param
/// param namen 模式串的字符个数 /param
/// param namenext next数组的首元素地址 /param
void getNext(char* s, int n, int* next)
{//i用来遍历模式串j用来为next数组赋值并且查找最长公共前后缀int i 1, j 0;//next[1]需要直接赋值next[1] 0;while (i n){if (j 0 || s[i] s[j])next[i] j;elsej next[j];}
}
int main()
{char a[10] abababde;char s[5] aba;int next[4];getNext(s, 3, next);//8是主串的长度哈for (int i 1, j 0; i 8; i){while (j a[i] ! s[j1])j next[j];if (a[i] s[j1])j;//3是模式串的字符个数相等就代表找到了if (j 3){//输出开始匹配的位置printf(%d , i - j 1);//更新j尝试找到更多解j next[j];}}return 0;
}下面就是字符串从0开始存储的代码同样的哈代码版本有很多重要的是理解思路void getNext(char* s, int n, int* next)
{int i 0, j -1;next[0] -1;while (i n){if (j -1 || s[i] s[j])next[i] j;elsej next[j];}
}int main()
{char a[9] abababde;char b[5] abab;int next[5];getNext(b, 4, next);for (int i 0, j 0; i 8; i){while (j a[i] ! b[j])j next[j];if (a[i] b[j])j;if (j 4){printf(%d , i - j 1);j next[j];}}return 0;
}小试牛刀下面的题解法肯定不止一种kmp算法也不一定是最简单的但是阔以用来练习kmp算法的3.1 旋转字符串796. 旋转字符串 - 力扣LeetCode题目描述给定两个字符串, s 和 goal。如果在若干次旋转操作之后s 能变成 goal 那么返回 true。s 的 旋转操作 就是将 s 最左边的字符移动到最右边。 例如, 若 s abcde在旋转一次之后结果就是bcdea 。用kmp解题的大致思路就是拼接一个字符串到s后面将goal当成模式串在拼接后的字符串中查找goal就行。void getNext(char* neddle, int n,int*next)
{int i 0;int j -1;next[0] -1;while(in){if(j-1||neddle[i]neddle[j])next[i] j;elsej next[j];}
}
bool rotateString(char * s, char * goal){int lens strlen(s);int leng strlen(goal);if(lens!leng)return false;char*str (char*)calloc(lens*21, sizeof(char));memmove(str,s,lens);memmove(strlens,s,lens);int * next (int*)malloc(sizeof(int)*(leng1));getNext(goal, leng,next);for(int i 0,j0;ilens*2;i){while(jstr[i]!goal[j])j next[j];if(str[i]goal[j])j;if(jleng){return true;}}return false;
}3.2 最长快乐前缀1392. 最长快乐前缀 - 力扣LeetCode题目描述「快乐前缀」 是在原字符串中既是 非空 前缀也是后缀不包括原字符串自身的字符串。给你一个字符串 s请你返回它的 最长快乐前缀。如果不存在满足题意的前缀则返回一个空字符串 。void getNext(char*s,int n,int* next)
{int i 0;int j -1;next[0] -1;while(in){if(j-1||s[i]s[j])next[i] j;elsej next[j];}
}char * longestPrefix(char * s){int len strlen(s);int next[len1];getNext(s,len,next);int max 0;if(next[len]max)max next[len];if(max0)return ;else{char* ret (char*)calloc(max1,sizeof(char));for(int i 0;imax;i){ret[i] s[i];}return ret;}
}
