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

前言:力扣刷题

问题:

给你两个字符串 haystackneedle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1

示例:

输入:haystack = "sadbutsad", needle = "sad"
输出:0
解释:"sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。

思路:

看到这个题我就想到了我之前学过的KMP算法,这道题肯定要使用到KMP算法思想。

haystack为主串,needle是子串。

用于在字符串haystack中查找子串needle的第一次出现位置。算法使用了KMP算法中的next数组,用于记录子串中每个字符的最长相同前后缀长度。

具体来说,算法首先生成子串needle的next数组,然后使用两个指针ij分别指向字符串haystack和子串needle的第一个字符,然后开始遍历字符串。

如果当前字符匹配,则两个指针都后移一位;

如果不匹配,则将指向子串的指针j更新为已匹配的最长相同前后缀长度,然后继续比较;

如果子串的指针j已经到达末尾,则说明已经找到了匹配的子串,返回起始位置即可。

基于上述思考,代码如下:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def get_next():
            for i in range(1, n):
                k = next_[i - 1]
                while needle[i] != needle[k]:
                    if k == 0:
                        k -= 1
                        break
                    else:
                        k = next_[k - 1]
                    
                next_[i] = k + 1 
        
        n = len(needle)
        next_ = [0] * n
        get_next()

        i = 0
        j = 0
        while i < len(haystack):
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            elif j == 0:
                i += 1
            else:
                j = next_[j - 1]
            if j >= n:
                return i - n
        return -1

设索引i指向主串当前进行匹配的字符,索引j指向子串当前进行匹配的字符:

如果当前字符相同,那么两个索引都后一位,继续匹配
如果当前字符不同,且索引j = 0,说明第一个字符就不匹配,索引i后移一位。
如果当前字符不同,且索引j > 0,说明在索引i和j发生了失配,j移动到next[j]的位置继续匹配。

执行结果如下图:

image-20230918175513607.png

学习到的知识点:

温习KMP算法,哈哈哈还是考研的时候学习的KMP匹配算法,又想了好久才想起来🤣。

相关推荐

最近更新

  1. leetcode705-Design HashSet

    2024-04-03 12:26:02       5 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-03 12:26:02       5 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-03 12:26:02       6 阅读
  4. 高级IO——React服务器简单实现

    2024-04-03 12:26:02       5 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-03 12:26:02       4 阅读
  6. go第三方库go.uber.org介绍

    2024-04-03 12:26:02       6 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-03 12:26:02       7 阅读

热门阅读

  1. 分布式锁的几种实现方式

    2024-04-03 12:26:02       4 阅读
  2. 策略模式

    2024-04-03 12:26:02       3 阅读
  3. 策略模式详解+代码案例

    2024-04-03 12:26:02       3 阅读
  4. 洛谷 P1747 好奇怪的游戏

    2024-04-03 12:26:02       4 阅读
  5. 非关系型数据库Redis部署与常用命令

    2024-04-03 12:26:02       4 阅读
  6. 用 ipset 和 iptables 保护 sip 端口

    2024-04-03 12:26:02       4 阅读
  7. TCP

    TCP

    2024-04-03 12:26:02      4 阅读