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

文章介绍了如何使用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

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

小小的香辛料

你的鼓励将是我创作的最大动力

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付:¥1
获取中
扫码支付

您的余额不足,请更换扫码支付或充值

打赏作者

实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值