网站制作有哪些企业,app外包后期怎么维护,古风网站的关于我们页面怎么做,郑州影视公司【字符串匹配】【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 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 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;}
}
