网站设计轮播图需要吗,品牌网站建设找哪家,软件开发流程,wordpress简易主题、 #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 kmp算法找出字符串中第…、 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 kmp算法找出字符串中第一个匹配项的下标重复的子字符串移动匹配kmp算法 总结 kmp算法
kmp算法是一种快速查找字符串的算法主要用途是在一个字符串里查找是否包含另一个字符串kmp在理解上不是很友好首先我们要搞清楚什么是前后缀、最长相等前后缀、前缀表、next数组如何实现前缀表最后就是kmp算法借助前缀表的实现。 前后缀的概念 前缀就是包含第一个字符而不包含最后一个字符的所有字串都可以被称为前缀。
后缀是包含最后一个字符且不包含第一个字符的所有字串都可以被称为后缀。
举个例子:hello 前缀可以是h,he,hel,hell 后缀可以是e,el,ell,ello 最长相等前后缀 最长相等前后缀顾名思义就是前后缀相等的情况下我们取最长的那一段。 前缀表next数组如何实现 前缀表十分重要它是KMP算法的核心思想先说它的作用它的作用是实现匹配字符串时如果遇到主串用于对比的字符串和模式串拿来做对比的字符串某个字符不相等时将指针返回到上一个最长相等前后缀处再进行对比这样做的好处是可以使字符不相等时退回某处而不至于像暴力求解一样一遇到不相等就要重头对比在主串有一定规律时此方法显得十分方便。
下面我们再来说一说实现的方法 定义一个数组名字叫next数组网上大体有三种方法第一种就是数组正常存储返回地址第二种数组存储返回地址-1第三种将返回地址整体向左移动。
我们说到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]}
}这一段就是c的前缀表代码段我们用j来表示前缀的最长长度为多少i来向后遍历当我们这个字符串的两个位置不相等时判断j是否大于0因为要涉及到j-1只要两个位置不相等就使j一直回退如果两位置相等那么j向前走一步意为最长长度加1然后在数组每一个位置记录当前匹配失败时回退到那个位置。
关于kmp算法的使用我们来看具体的例题。
找出字符串中第一个匹配项的下标
28. 找出字符串中第一个匹配项的下标 - 力扣LeetCode
这道题就是典型可以应用kmp算法的题型
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;}
};第一部分的代码就是上面所说的前缀和后面的是用循环来遍历也就是应用前缀和数组next遍历查找如果两字符串某个字符不相等那么就使j一直回退相等时候j当j到模式串的最后一个字符了则说明该字符串在主串中由于字符不相同时只有j会回退i仍然向前走所以当i走完全部j还没有到到最后一个字符说明该字符串不存在于主串内。
重复的子字符串
459. 重复的子字符串 - 力扣LeetCode
移动匹配
判断字符串s是否由重复子串组成只要两个s拼接在一起里面还出现一个s的话就说明是由重复子串组成。当然我们在判断 s s 拼接的字符串里是否出现一个s的的时候要刨除 s s 的首字符和尾字符这样避免在ss中搜索出原来的s我们要搜索的是中间拼接出来的s。
class Solution {
public:bool repeatedSubstringPattern(string s) {string t s s;t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾if (t.find(s) ! std::string::npos) return true; // rreturn false;}
};kmp算法
这道题刚看的时候不太像使用kmp算法的题目但是可以用kmp算法其中是有一些技巧的字符串的相等前后缀错开的那一部分则为重复子串用该重复子串重复n次则可以取得原字符串。这个结论可以模拟一下。用next数组模拟数组中最后一位存取的就是最长前后缀的长度用字符串总长度对总长度减去最长前后缀的长度再取模如果能整除则该字符串是由前x个字符由n次变换得到若不能整除则说明字符串不是由重复字串得到的。这里使用了前缀表统一减一的实现方式
class Solution {
public:void getNext (int* next, const string s){next[0] -1;int j -1;for(int i 1;i s.size(); i){while(j 0 s[i] ! s[j 1]) {j next[j];}if(s[i] s[j 1]) {j;}next[i] j;}}bool repeatedSubstringPattern (string s) {if (s.size() 0) {return false;}int next[s.size()];getNext(next, s);int len s.size();if (next[len - 1] ! -1 len % (len - (next[len - 1] 1)) 0) {return true;}return false;}
};总结
今天我们进行了字符串的复习和双指针的回顾还有kmp算法的应用kmp算法还是挺有难度的相关的思想需要多复习回顾。接下来我们继续进行算法练习·。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
