• (※)力扣刷题-字符串-实现 strStr()(KMP算法)


    28 实现 strStr()

    实现 strStr() 函数。
    给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
    示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2
    示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1
    说明: **当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。 对于本题而言,当 needle 是空字符串时我们应当返回 0 **。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

    思路

    首先是模式串匹配问题,需要先在hatstack(文本串)中找到needle子串(模式串),然后再去考虑求这个索引。第一个问题就涉及到KMP算法。KMP的经典思想就是:当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息避免从头再去做匹配。
    以下代码随想录文字详细说明了KMP算法:
    https://www.programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E6%80%9D%E8%B7%AF

    解法一-前缀表(减一)

    class Solution(object):
        # 第一步 首先要求next数组
        def getNext(self, next, s): # s表示模式串
            # 初始化
            j = -1
            next[0] = j
            for i in range(1, len(s)): # 注意i从1开始 因为要比较 i 和 j是否相同
                # 前后缀不相同 
                while j>=0 and s[i]!=s[j+1]:
                    j = next[j] # j回退
                # 前后缀相同
                if s[i]==s[j+1]:
                    j += 1 # i和j都加1
                next[i] = j
    
        # 第二步 求下标索引
        def strStr(self, haystack, needle):
            """
            :type haystack: str
            :type needle: str
            :rtype: int
            """
            if not needle:
                return 0
            next = [0]*len(needle) # 初始化next
            self.getNext(next, needle)
            j = -1
            for i in range(len(haystack)):
                while j >= 0 and haystack[i]!=needle[j+1]: # j+1是因为j初始值为-1
                    j = next[j] # next数组起作用了 找下一个匹配的位置
                if haystack[i]==needle[j+1]: # 匹配到字符相同
                    j += 1
                # 判断在文本串里出现了模式串
                if j == len(needle) - 1:
                    return i - len(needle) + 1 # 返回索引
            return -1
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    暴力法

    class Solution(object):
        def strStr(self, haystack, needle):
            """
            :type haystack: str
            :type needle: str
            :rtype: int
            """
            m, n = len(haystack), len(needle)
            for i in range(m):
                if haystack[i:i+n] == needle:
                    return i
            return -1   
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    使用index(写算法题不推荐)

    class Solution:
        def strStr(self, haystack: str, needle: str) -> int:
            try:
                return haystack.index(needle)
            except ValueError:
                return -1
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    使用find(写算法题不推荐)

    class Solution:
        def strStr(self, haystack: str, needle: str) -> int:
            return haystack.find(needle)
    
    • 1
    • 2
    • 3
  • 相关阅读:
    【MM32F5270开发板试用】基于MindSDK实现水深度数据采集
    再谈Java泛型
    行业洞察 | 听说,大语言模型无法接近人类水平智能?
    “事后达尔文”—— 游戏业务效果评估方法实践
    Linux的目录结构(介绍主要的)
    Java版企业工程项目管理系统源码+java版本+项目模块功能清单+spring cloud +spring boot
    rsync远程同步
    小程序引入vant-Weapp保姆级教程及安装过程的问题解决
    聊聊二叉树的前序遍历算法
    【超简单实用】Zotero 7 内置pdf背景颜色更改插推荐以及安装
  • 原文地址:https://blog.csdn.net/hxhabcd123/article/details/133819191