毕业设计指导网站建设,东莞广告公司东莞网站建设,网站建设素材图片,wordpress编辑文章更新失败leetcode28. 实现 strStr#xff08;#xff09; 1 题目2 KMP2.1 什么是KMP#xff1f;2.2 KMP有什么用#xff1f;2.3 什么是前缀表#xff1f;2.4 最长公共前后缀2.5 为什么一定要用前缀表#xff1f;2.6 如何计算前缀表2.7 前缀表与next数组2.8 使用next数组来匹配2.9…
leetcode28. 实现 strStr 1 题目2 KMP2.1 什么是KMP2.2 KMP有什么用2.3 什么是前缀表2.4 最长公共前后缀2.5 为什么一定要用前缀表2.6 如何计算前缀表2.7 前缀表与next数组2.8 使用next数组来匹配2.9 时间复杂度分析3 KMP代码思路3.1 构造next数组3.2 使用next数组来做匹配4 代码4.1 C4.2 C版本4.3 Java版本4.4 Python版本4.5 JavaScript版本5 总结在一个串中查找是否出现过另一个串这是KMP的看家本领。 1 题目 题源链接
给你两个字符串 haystack 和 needle 请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标下标从 0 开始。如果 needle 不是 haystack 的一部分则返回 -1 。
示例 1
输入haystack “sadbutsad”, needle “sad” 输出0 解释“sad” 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 所以返回 0 。 示例 2
输入haystack “leetcode”, needle “leeto” 输出-1 解释“leeto” 没有在 “leetcode” 中出现所以返回 -1 。
提示
1 haystack.length, needle.length 104 haystack 和 needle 仅由小写英文字符组成 2 KMP 下面是Carl老师的视频讲解 帮你把KMP算法学个通透理论篇 帮你把KMP算法学个通透求next数组代码篇
KMP的经典思想就是:当出现字符串不匹配时可以记录一部分之前已经匹配的文本内容利用这些信息避免从头再去做匹配。 2.1 什么是KMP
为什么叫做KMP呢。
因为是由这三位学者发明的KnuthMorris和Pratt所以取了三位学者名字的首字母。所以叫做KMP。 2.2 KMP有什么用
KMP主要应用在字符串匹配上。
KMP的主要思想是当出现字符串不匹配时可以知道一部分之前已经匹配的文本内容可以利用这些信息避免从头再去做匹配了。
所以如何记录已经匹配的文本内容是KMP的重点也是next数组肩负的重任。 2.3 什么是前缀表
next数组就是一个前缀表prefix table。
前缀表有什么作用呢
前缀表是用来回退的它记录了模式串与主串(文本串)不匹配的时候模式串应该从哪里开始重新匹配。
为了清楚地了解前缀表的来历我们来举一个例子
要在文本串aabaabaafa 中查找是否出现过一个模式串aabaaf。
请记住文本串和模式串的作用。 动画演示
文本串中第六个字符b 和 模式串的第六个字符f不匹配了。如果暴力匹配发现不匹配此时就要从头匹配了。
但如果使用前缀表就不会从头匹配而是从上次已经匹配的内容开始匹配找到了模式串中第三个字符b继续开始匹配。
前缀表是如何记录的呢
前缀表的任务是当前位置匹配失败找到之前已经匹配上的位置再重新匹配此也意味着在某个字符失配时前缀表会告诉你下一步匹配中模式串应该跳到哪个位置。
那么什么是前缀表记录下标i之前包括i的字符串中有多大长度的相同前缀后缀。 2.4 最长公共前后缀
字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
可以将最长公共前后缀理解为最长相等前后缀因为前缀表要求的就是相同前后缀的长度。
所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等… 2.5 为什么一定要用前缀表
刚刚匹配的过程在下标5的地方遇到不匹配模式串是指向f如图 然后就找到了下标2指向b继续匹配如图 下标5之前这部分的字符串也就是字符串aabaa的最长相等的前缀 和 后缀字符串是 子字符串aa 因为找到了最长相等的前缀和后缀匹配失败的位置是后缀子串的后面那么我们找到与其相同的前缀的后面重新匹配就可以了。
所以前缀表具有告诉我们当前位置匹配失败跳到之前已经匹配过的地方的能力。 2.6 如何计算前缀表 长度为前1个字符的子串a最长相同前后缀的长度为0。注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。 长度为前2个字符的子串aa最长相同前后缀的长度为1。 长度为前3个字符的子串aab最长相同前后缀的长度为0。
以此类推 长度为前4个字符的子串aaba最长相同前后缀的长度为1。 长度为前5个字符的子串aabaa最长相同前后缀的长度为2。 长度为前6个字符的子串aabaaf最长相同前后缀的长度为0。
那么把求得的最长相同前后缀的长度就是对应前缀表的元素如图 可以看出模式串与前缀表对应位置的数字表示的就是下标i之前包括i的字符串中有多大长度的相同前缀后缀。
再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示 动画演示 找到的不匹配的位置 那么此时我们要看它的前一个字符的前缀表的数值是多少。
因为要找前面字符串的最长相同的前缀和后缀。
所以要看前一位的 前缀表的数值。
前一个字符的前缀表的数值是2 所以把下标移动到下标2的位置继续比配。 可以再反复看一下上面的动画。
最后就在文本串中找到了和模式串匹配的子串了。 2.7 前缀表与next数组
很多KMP算法的时间都是使用next数组来做回退操作那么next数组与前缀表有什么关系呢
next数组就可以是前缀表但是很多实现都是把前缀表统一减一右移一位初始位置为-1之后作为next数组。
其实这并不涉及到KMP的原理而是具体实现next数组既可以就是前缀表也可以是前缀表统一减一右移一位初始位置为-1。 2.8 使用next数组来匹配
以下我们以前缀表统一减一之后的next数组来做演示。
有了next数组就可以根据next数组来 匹配文本串s和模式串t了。
注意next数组是新前缀表旧前缀表统一减一了。
匹配过程动画如下 动画演示 2.9 时间复杂度分析
其中n为文本串长度m为模式串长度因为在匹配的过程中根据前缀表不断调整匹配的位置可以看出匹配的过程是O(n)之前还要单独生成next数组时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(nm)的。
暴力的解法显而易见是O(n × m)所以KMP在字符串匹配中极大地提高了搜索的效率。 3 KMP代码思路 3.1 构造next数组
定义一个函数getNext来构建next数组函数参数为指向next数组的指针和一个字符串。 代码如下
void getNext(int* next, const string s)构造next数组其实就是计算模式串s前缀表的过程。 主要有如下三步
初始化处理前后缀不相同的情况处理前后缀相同的情况 1. 初始化
定义两个指针i和jj 指向前缀末尾位置i 指向后缀末尾位置。
然后还要对next数组进行初始化赋值如下 j 为什么要初始化为 -1呢因为之前说过 前缀表要统一减一的操作仅仅是其中的一种实现我们这里选择j初始化为-1
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) {如果 s[i] 与 s[j1]不相同也就是遇到 前后缀末尾不相同的情况就要向前回退。
next[j]就是记录着j包括j之前的子串的相同前后缀的长度。 那么 s[i] 与 s[j1] 不相同就要找 j1前一个元素在next数组里的值就是next[j]。
所以处理前后缀不相同的情况代码如下
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数组的逻辑流程动画如下 动画演示 3.2 使用next数组来做匹配
在文本串s里 找是否出现过模式串t。
定义两个下标j 指向模式串起始位置i指向文本串起始位置。
那么j初始值依然为-1为什么呢 依然因为next数组里记录的起始位置为-1。
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];
}如果j指向了模式串t的末尾那么就说明模式串t完全匹配文本串s里的某个子串了。
本题要在文本串字符串中找出模式串出现的第一个位置 (从0开始)所以返回当前在文本串匹配模式串的位置i 减去 模式串的长度就是文本串字符串中出现模式串的第一个位置。
使用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);}
}4 代码 4.1 C
class Solution {
public:void getNext(int* next, const string s) {int j -1;next[0] j;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; //将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; for (int i 0; i haystack.size(); i) {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;}
};4.2 C版本
int strStr(char * haystack, char * needle){int hLen strlen(haystack);int nLen strlen(needle);int *next (int *)malloc(nLen*sizeof(int));int j -1;next[0] j;//求next数组for (int i 1; i nLen; i) {while (j 0 needle[i] ! needle[j1]) {j next[j];}if (needle[i] needle[j 1])j;next[i] j;}//匹配j -1;for (int i 0; i hLen; i) {while (j 0 haystack[i] ! needle[j1])j next[j];if (haystack[i] needle[j1])j;if (j nLen - 1)return (i - nLen 1);}return -1;
}4.3 Java版本
class Solution {public void getNext(int[] next, String s) {int j -1;next[0] j;for (int i 1; i s.length(); i) {while (j 0 s.charAt(i) ! s.charAt(j 1)) //处理不匹配的情况j next[j];if (s.charAt(i) s.charAt(j 1)) //处理匹配的情况j和i都向后移j; //i的增加在for里next[i] j;}}public int strStr(String haystack, String needle) {if (needle.length() 0) return 0;int [] next new int[needle.length()];getNext(next, needle);int j -1;for (int i 0; i haystack.length(); i) {while (j 0 haystack.charAt(i) ! needle.charAt(j 1) )j next[j];if (haystack.charAt(i) needle.charAt(j 1))j;if(j needle.length() - 1)return i - needle.length() 1;}return -1;}
}4.4 Python版本
class Solution:def strStr(self, haystack: str, needle: str) - int:a len(needle)b len(haystack)if a 0:return 0next self.getnext(a,needle)p-1for j in range(b):while p 0 and needle[p1] ! haystack[j]:p next[p]if needle[p1] haystack[j]:p 1if p a-1:return j-a1return -1def getnext(self,a,needle):next [ for i in range(a)]k -1next[0] kfor i in range(1, len(needle)):while (k -1 and needle[k1] ! needle[i]):k next[k]if needle[k1] needle[i]:k 1next[i] kreturn next4.5 JavaScript版本
/*** param {string} haystack* param {string} needle* return {number}*/
var strStr function (haystack, needle) {if (needle.length 0)return 0;const getNext (needle) {let next [];let j -1;next.push(j);for (let i 1; i needle.length; i) {while (j 0 needle[i] ! needle[j 1])j next[j];if (needle[i] needle[j 1])j;next.push(j);}return next;}let next getNext(needle);let j -1;for (let i 0; i haystack.length; i) {while (j 0 haystack[i] ! needle[j 1])j next[j];if (haystack[i] needle[j 1])j;if (j needle.length - 1)return (i - needle.length 1);}return -1;
};5 总结 在一个串中查找是否出现过另一个串这是KMP的看家本领。 扩展知识点就是next数组还可以优化为nextval数组。这里不做过多介绍。往年408 数据结构与算法中会有考察到。 可以参考王道。
下面是Carl老师的视频讲解 帮你把KMP算法学个通透理论篇 帮你把KMP算法学个通透求next数组代码篇
KMP的经典思想就是:当出现字符串不匹配时可以记录一部分之前已经匹配的文本内容利用这些信息避免从头再去做匹配。 By Suki 2023/3/2
