【代码随想录day9】KMP算法-找出字符串中第一个匹配项的下标-CSDN博客

本文链接：https://blog.csdn.net/doubleguy/article/details/131708257

文章介绍了如何使用KMP算法进行字符串匹配，首先计算模式串的next数组，然后利用next数组优化匹配过程，降低时间复杂度至O(m+n)。在给定的示例中，算法会返回目标字符串中模式串首次出现的位置，或者在未找到时返回-1。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

给你两个字符串 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算法，是我见过代码讲的最清楚的了（点赞）。

我们的目标是文本串中找到模式串，并返回它在文本串中出现的首位值。

主要思路是第一步求出模式串的next数组（其实也就是模式串最大公共前后缀长度值）第二步是利用next数组优化字符串匹配过程，从而降低复杂度。

最后只要是字符串匹配相关得算法题，都可以用kmp优化，相比暴力得o(n*m)时间复杂度，KMP将时间复杂度降为了o(m+n)，简直不要太快，强烈推荐掌握！

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # 目标是从文本串中找到模式串是否出现过，如果出现则返回出现的第一个位置
        # 1.得到模式串的next数组（也就是前缀表）
        def get_next(s):
            next = [0]*len(s)
            j = -1
            next[0] = j
            # i指向后缀的结束位置(包含结束位置)，j指向前缀的结束位置(包含结束位置)
            for i in range(1,len(next)):
                # 前后缀不相同，将j指针回溯，直到找到与后缀相同的字符或者j==-1
                while j>=0 and s[j+1]!=s[i]:
                    j = next[j]
                # 前后缀相同，i和j同时往后移动，i的移动在for循环中
                if s[j+1] == s[i]:
                    j += 1
                next[i] = j
            return next

        # 2.通过next数组优化字符串匹配过程
        next = get_next(needle)
        j = -1
        for i in range(len(haystack)):
            # 文本串与模式串不匹配
            while j>=0 and haystack[i]!=needle[j+1]:
                j = next[j]
            # 文本串与模式串匹配，i和j都右移，其中i的右移包含在for循环中了
            if haystack[i] == needle[j+1]:
                j += 1
            # 模式串已经匹配完毕，返回即可
            if j == len(needle)-1:
                return i-len(needle)+1
        return -1