28.找出字符串中第一个匹配项的下标给你两个字符串 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 104haystack 和 needle 仅由小写英文字符组成实现代码Python:classSolution(object):defgetNext(self,next,needle):#j:表示当前已匹配的最长相等前缀的最后一个位置#i:表示当前正在处理的后缀的最后一个位置#1.初始化j-1next[0]j#2.处理前后缀不相同的情况回退foriinrange(1,len(needle)):whilej0andneedle[i]!needle[j1]:jnext[j]#3.处理前后缀相同的情况:前进ifneedle[i]needle[j1]:j1#4.更新next[i]jreturnnextdefstrStr(self,haystack,needle): :type haystack: str :type needle: str :rtype: int iflen(haystack)0:return-1next[-1]*len(needle)self.getNext(next,needle)j-1#j:模式串指针foriinrange(len(haystack)):#i:主串指针whilej0andhaystack[i]!needle[j1]:jnext[j]ifhaystack[i]needle[j1]:j1ifjlen(needle)-1:returni-len(needle)1return-1核心思路——KMP算法解决字符串问题最常用的算法就是KMP算法通过预处理next数组当匹配失败时主串指针不动模式串指针根据next数组略过一些字符继续匹配可以避免回溯