网站开发职业生涯规划范文,建网站哪家划算,智能小程序下载,智慧团建官网重置密码验证码【字符串匹配】【KMP算法】Leetcode 28 找出字符串中第一个匹配项的下标 #xff08;1#xff09;前缀和后缀#xff08;2#xff09;前缀表#xff08;最长相同的前缀和后缀的长度#xff09;#xff08;3#xff09;匹配过程示意#xff08;4#xff09;next数组的… 【字符串匹配】【KMP算法】Leetcode 28 找出字符串中第一个匹配项的下标 1前缀和后缀2前缀表最长相同的前缀和后缀的长度3匹配过程示意4next数组的实现方法1.初始化2.处理前后缀不相等的情况 :3.处理前后缀相同的情况4.求next数组的程序 题目做法解法1 KMP算法解法2 暴力做法 ---------------题目链接------------------- 任务要在文本串aabaabaafa 中查找是否出现过一个模式串aabaaf
1前缀和后缀
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。 比如aabaaf的前缀包括a,aa,aab,aaba,aabaa 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。 比如aabaaf的后缀包括f,af,aaf,baaf,abaaf
2前缀表最长相同的前缀和后缀的长度
前缀表最长相同的前缀和后缀的长度 前缀表最长相同的前缀和后缀的长度 前缀表最长相同的前缀和后缀的长度 作用记录下标i之前包括i的字符串中有多大长度的相同前缀后缀
模式串aabaaf的前缀表
字符串最长相等前后缀a0aa1aab0aaba1aabaa2aabaaf0
前缀表的任务当前位置匹配失败找到之前已经匹配上的位置再重新匹配。 也意味着在某个字符失配时前缀表会告诉你下一步匹配中模式串应该跳到哪个位置。
文本串aabaabaaf模式串下标012345模式串aabaaf–前缀表–010120
当匹配到 b 的时候模式串为 f 匹配失败。 于是寻找 f 前面的字符串 aabaa 他的最长相等前缀和后缀字符串是 aa 因为找到了最长相等的前缀和后缀匹配失败的位置是后缀子串的后面那么我们找到与其相同的前缀的后面即前缀表中发现冲突位置的前面的字符串——aabaa对应的前缀表为【2】因此找到模式串中下标索引为【2】的位置 —— b 的位置开始重新匹配就可以了。
文本串aabaabaaf模式串aabaaf
3匹配过程示意 4next数组的实现方法 next数组详解视频 代码随想录文字版 代码随想录视频版本
1.初始化
【i后缀的末尾】初始化为1 【j前缀的末尾】初始化为0 next [ 0 ] 0 j也代表了i包括i之前的字符串的最长相等前后缀长度
2.处理前后缀不相等的情况 :
j连续回退 ———— jnext [ j-1 ], 在j大于0的情况下3.处理前后缀相同的情况
j → 更新next数组next [ i ] j → i4.求next数组的程序
1.初始化 【i后缀的末尾】初始化为1 【j前缀的末尾也代表i包括i前字符的最长相等前后缀长度】初始化为0 next[0] 0
2.处理前后缀不相等的情况
3.处理前后缀相同的情况//求前缀表nextprivate void getNext(int[] next, String s){int j 0; // 初始化j为前缀末尾0,i为后缀的末尾next[0] 0;for(int i 1; i s.length(); i){ while(j 0 s.charAt(j) ! s.charAt(i)){ j next[j-1];}if(s.charAt(j) s.charAt(i)){ // 如果相同前缀末尾jj;}next[i] j; // 将前缀的长度给next[i]}} 题目做法
解法1 KMP算法
时间复杂度O(N) 空间复杂度O(N) class Solution {public int strStr(String haystack, String needle) {if(haystack.length() needle.length()) return -1;int[] next new int[needle.length()];getNext(next, needle);int j 0;for(int i 0; i haystack.length(); i){while(j0 needle.charAt(j) ! haystack.charAt(i)){ j next[j-1];}if(needle.charAt(j) haystack.charAt(i)){j;}if(j needle.length()) {return i-needle.length()1;}}return -1;}//求前缀表nextprivate void getNext(int[] next, String s){int j 0; // 初始化j为前缀末尾0,i为后缀的末尾next[0] 0;for(int i 1; i s.length(); i){ while(j 0 s.charAt(j) ! s.charAt(i)){ j next[j-1];}if(s.charAt(j) s.charAt(i)){ // 如果相同前缀末尾jj;}next[i] j; // 将前缀的长度给next[i]}}
}解法2 暴力做法 从大字符串的第一个元素开始比对小字符串一旦出现不一样的就从大字符串的下一个元素开始进行比对 如果小字符串遍历结束时都一样则return对应的下标 如果大字符串遍历完小字符串还没遍历完return-1 遍历完大字符串前都找不到的话就return -1 时间复杂度O(N^2) 空间复杂度O(N)
class Solution {public int strStr(String haystack, String needle) {// 暴力做法char[] ch1 haystack.toCharArray();char[] ch2 needle.toCharArray();int result -1;for(int i 0; i ch1.length; i){ // haystack的遍历if(ch1[i] ch2[0]){int outside i;int inside 0;while(ch1[outside] ch2[inside]){outside;inside;if(inside ch2.length){return outside-ch2.length;}else if(outside ch1.length){return result;}}}}return result;}
}
