28. 找出字符串中第一个匹配项的下标

• 题目
• 法一、KMP
• 法二、切片
• 法三、两行

题目

• 给你两个字符串 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 。

法一、KMP

• kmp算法讲的比较清楚的一篇博客：https://blog.csdn.net/qq_62982856/article/details/128003067
• 步骤：根据字串字符构造一个next数组；遍历主串字符串，当匹配失败，查询next数组，定位字串，接着与主串比较

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def getNext(p):
            _next = [0] * (len(p)+1) #初始化next数组
            _next[0] = -1
            i,j = 0,-1
            while i  <len (p):
                if j==-1 or p[i] == p[j]:#如果j==-1或者两个指针的值相等
                    i+=1#i前进1步：匹配上了
                    j+=1#j前进1步:长度加1
                    _next[i]=j#把长度存进当前next数组
                else:#如果两个指针的值不相等
                    j=_next[j]#回到头部位置
          
            return _next
            
        def kmp(s,p,_next):
            i=j=0#i遍历主串j遍历子串
            while i<len(s) and j<len(p):
                if j==-1 or s[i]==p[j]:#匹配上了
                    i += 1#主串指针后移1位
                    j += 1#子串指针后移1位
                else:#匹配失效
                    #主串指针不动，子串指针查next数组进行移动
                    j=_next[j]
          
            if j==len(p):#字串走完了，每一个字母都匹配
                return i-j#返回主串中第一次出现子串的下标
            else:
                return -1
        return kmp(haystack,needle,getNext(needle))

法二、切片

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle in haystack:#先用in判断needle是否在haystack里
            for i in range(len(haystack)):#遍历haystack
                if haystack[i] == needle[0]:#找到与needle第一个字母相同的地方
                    if haystack[i:i+len(needle)] == needle:#再对haystack切片needle的长度，如果等于needle就返回答案了，如果不相等，就继续遍历。
                        return i
        else:#如果needle是否在haystack里直接返回-1
            return -1

法三、两行

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        try:
            return haystack.index(needle)
        except:
            return -1