【pythonJava】leetcode.28.找出字符中第一个匹配项的下标代码随想录刷题笔记-字符串-6.实现strStr()题目要求给你两个字符串 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 仅由小写英文字符组成思路利用kmp算法进行匹配Java//kmp,next数组初始为-1classSolution{publicintstrStr(Stringhaystack,Stringneedle){if(needle.length()0){return0;}int[]nextnewint[needle.length()];getNext(next,needle);//获取kmp中的next数组-前缀表intj-1;for(inti0;ihaystack.length();i){while(j0haystack.charAt(i)!needle.charAt(j1)){jnext[j];}if(haystack.charAt(i)needle.charAt(j1)){j;}if(jneedle.length()-1){return(i-needle.length()1);}}return-1;}publicvoidgetNext(int[]next,Strings){intj-1;next[0]j;for(inti1;is.length();i){while(j0s.charAt(i)!s.charAt(j1)){jnext[j];}if(s.charAt(i)s.charAt(j1)){j;}next[i]j;}}}pythonclassSolution:defstrStr(self,haystack:str,needle:str)-int:ifnotneedle:return0# 初始化next数组长度与模式串一致next_arr[0]*len(needle)self.get_Next(next_arr,needle)# j 初始化为 -1j-1# 对主串haystcak进行遍历foriinrange(len(haystack)):# 核心回退逻辑whilej0andhaystack[i]!needle[j1]:jnext_arr[j]# 匹配成功ifhaystack[i]needle[j1]:j1# j 到达模式串尾匹配成功ifjlen(needle)-1:returni-len(needle)1#遍历结束未找到返回-1return-1defget_Next(self,next_arr:list[int],s:str)-None:j-1next_arr[0]j# 从1开始遍历模式串foriinrange(1,len(s)):# 当前后缀不相同向前回退whilej0ands[i]!s[j1]:jnext_arr[j]# 找到相同的后缀ifs[i]s[j1]:j1next_arr[i]j