字符串匹配算法:KMP

这篇具有很好参考价值的文章主要介绍了字符串匹配算法:KMP。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Knuth–Morris–Pratt(KMP)是由三位数学家克努斯、莫里斯、普拉特同时发现,所有人们用三个人的名字来称呼这种算法,KMP是一种改进的字符串匹配算法,它的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。它的时间复杂度是 O(m+n)

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

在介绍KMP算法之前,我们先看一下另一种暴力算法(BF算法)去解字符匹配应该怎么做

字符串匹配算法:KMP

 BF算法:时间复杂度O(m*n)

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        #hi是haystack的当前索引
        hi = 0
        haystackLength = len(haystack)
        needleLength = len(needle)
        for i in range(haystackLength - needleLength+1):
            #每次匹配等于和完整的needle的字符串逐一匹配
            if haystack[i:i+needleLength] == needle:
                return i
        return -1

KMP算法:时间复杂度O(m+n)

KMP构造了一个next列表来对应改位置索引如果匹配失败应该追溯回到什么位置,这样我们讲减少了匹配次数

字符串匹配算法:KMP

 那么我们如何去构造维护我们的next(最长相同前后缀)

构造方法为:next[i] 对应的下标,为 P[0...i - 1] 的最长公共前缀后缀的长度,令 next[0] = -1 具体解释如下:

例如对于字符串 abcba:
    前缀:它的前缀包括:a, ab, abc, abcb,不包括本身;
    后缀:它的后缀包括:bcba, cba, ba, a,不包括本身;
    最长公共前缀后缀:abcba 的前缀和后缀中只有 a 是公共部分,字符串 a 的长度为 1

我们通过动态规划来维护next,假设你知道next[0:i-1]位置上所有的回溯值,那么next[i-1]和next[i]相比仅仅多了一个位置,如果这个多的字符可以匹配上,那么next[i]一定等于next[i-1]+1(如下图所示)

字符串匹配算法:KMP

那么如果匹配不上呢,匹配不上我们回溯到next[i-1]所需要回溯的位置,直到可以匹配上或到达无法追溯的位置next[0] = -1

    @staticmethod
    def same_start_end_str(p):
        """
        通过needle串来知道每个索引位置对应的最长前后缀
        例如ababa的最长前后缀是aba,前后缀是不和needle等长的最长相同前后缀
        """
        next = [-1] * (len(p)+1)
        si = -1
        ei = 0
        pl = len(p)
        while ei < pl :
            if si == -1 or p[si] == p[ei]:
                si += 1
                ei += 1
                next[ei] = si
            else:
                #无法匹配上,继续向前追溯
                si = next[si]

        return next

那我们有了next就可以取实现我们KMP算法了,完整代码如下

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        next = self.same_start_end_str(needle)
        #hi是haystack当前索引,ni是needle当前索引
        hi = ni = 0
        hl = len(haystack)
        nl = len(needle)
        while hi < hl and ni < nl:
            if ni == -1 or haystack[hi] == needle[ni]:
                hi += 1
                ni += 1
            else:
                ni = next[ni]

        if ni == nl:
            return hi - ni
        else:
            return -1

    @staticmethod
    def same_start_end_str(p):
        """
        通过needle串来知道每个索引位置对应的最长前后缀
        例如ababa的最长前后缀是aba,前后缀是不和needle等长的最长相同前后缀
        """
        next = [-1] * (len(p)+1)
        si = -1
        ei = 0
        pl = len(p)
        while ei < pl :
            if si == -1 or p[si] == p[ei]:
                si += 1
                ei += 1
                next[ei] = si
            else:
                #无法匹配上,继续向前追溯
                si = next[si]

        return next

 文章来源地址https://www.toymoban.com/news/detail-741783.html

到了这里,关于字符串匹配算法:KMP的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】字符串匹配|BF算法|KMP算法|next数组的优化

    字符串匹配算法是在实际工程中经常遇到的问题,也是各大公司笔试面试的常考题目,本文主要介绍BF算法(最好想到的算法,也最好实现)和KMP算法(最经典的) BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标S的第一个字符与模式串T的第一

    2024年02月04日
    浏览(56)
  • C#,字符串匹配(模式搜索)KMP算法的源代码与数据可视化

      D.E.Knuth   J.H.Morris KMP 算法(Knuth-Morris-Pratt 算法)是其中一个著名的、传统的字符串匹配算法,效率比较高。 KMP算法由 D.E.Knuth , J.H.Morris 和 V.R.Pratt 在 Brute-Force 算法的基础上提出的模式匹配的改进算法。因此人们称它为“克努特—莫里斯—普拉特算法”,简称KMP算法。K

    2024年01月25日
    浏览(55)
  • P3375 【模板】KMP 字符串匹配

    给出两个字符串 s 1 s_1 s 1 ​ 和 s 2 s_2 s 2 ​ ,若 s 1 s_1 s 1 ​ 的区间 [ l , r ] [l, r] [ l , r ] 子串与 s 2 s_2 s 2 ​ 完全相同,则称 s 2 s_2 s 2 ​ 在 s 1 s_1 s 1 ​ 中出现了,其出现位置为 l l l 。 现在请你求出 s 2 s_2 s 2 ​ 在 s 1 s_1 s 1 ​ 中所有出现的位置。 定义一个字符串 s s s 的

    2024年02月14日
    浏览(54)
  • PTA 7-1 字符串模式匹配(KMP)

    给定一个字符串 text 和一个模式串 pattern,求 pattern 在text 中的出现次数。text 和 pattern 中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern 可重叠。 输入格式: 输入共两行,分别是字符串text 和模式串pattern。 输出格式: 输出一个整数,表示 pattern 在 text 中的出

    2024年02月06日
    浏览(42)
  • 【leetcode 力扣刷题】字符串匹配之经典的KMP!!!

    以下是能用KMP求解的算法题,KMP是用于字符串匹配的经典算法【至今没学懂………啊啊啊】 题目链接:28. 找出字符串中第一个匹配项的下标 题目内容: 题意还是很好理解的,要在字符串haystack中查找一个完整的needle,即字符串匹配。 暴力求解就是用 两层循环 :haystack从第

    2024年02月09日
    浏览(42)
  • Leetcode的AC指南 —— 字符串/KMP:28.找出字符串中第一个匹配项的下标

    摘要: Leetcode的AC指南 —— 字符串/KMP:28.找出字符串中第一个匹配项的下标 。题目介绍:给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。 题目介绍 :给你两

    2024年02月02日
    浏览(55)
  • 数据结构--字符串的KMP算法

    朴素模式匹配算法: 一旦发现当前这个子串中某个字符不匹配,就只能转而匹配下一个子串(从头开始) 但我们可以知道: 不匹配的字符之前,一定是和模式串一致的 color{red}不匹配的字符之前,一定是和模式串一致的 不匹配的字符之前,一定是和模式串一致的 我们可以利用

    2024年02月12日
    浏览(64)
  • LeetCode:459. 重复的子字符串 —【2、KMP算法】

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。 来源:力扣(LeetCode) 难度: 简单 提示: 1 = s.length = 104 s 由小写英文字母组成 示例 1: 输入:

    2024年02月04日
    浏览(82)
  • 代码随想录 Leetcode459. 重复的子字符串(KMP算法)

            此解法读者需要了解什么是KMP算法以及KMP算法中next数组的具体含义才能理解         因为在KMP算法的next数组中,next[index]表示 i ndex之前的最大长度的相同前缀后缀值 ,那么要判断整个字符串中是否由重复字串构成,只需要以下两个条件:         1.next[n - 1] !=

    2024年01月19日
    浏览(78)
  • 【字符串匹配】暴力匹配算法

    ​ 暴力匹配算法,也称为朴素字符串匹配算法,是一种简单但不高效的字符串匹配方法。它的原理非常直观,其主要思想是逐个字符地比较文本串和模式串,从文本串的每个可能的起始位置开始,依次检查是否有匹配的子串。以下是暴力匹配算法的详细原理: 1. 一个字一个

    2024年02月09日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包