python算法-字符串查找KMP算法

刺骨的言语ヽ痛彻心扉 2022-05-30 22:10 204阅读 0赞

问题：对于一个给定非空的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 `-1`。

def patten_str(t, p):
        n = len(t)
        m = len(p)
        pi = compute_prefix_function(p)
        q = 0
        if t == p:
            return 0
    
        for i in range(n):
            print(p[q], t[i])
            if p[q] == t[i]:
                q = q + 1
            else:
                if pi[q] == 0:
                    q = 0
                else:
                    q = pi[q] - 1
    
                if p[q] == t[i]:
                    q = q + 1
    
            if q == m:
                return i - m + 1
    
        return -1
    
    
    def compute_prefix_function(p):
        m = len(p)
        pi = [0] * m
        k = 0
        for q in range(1, m):
            if p[k] == p[q]:
                k = k + 1
            else:
                k = 0
                if p[k] == p[q]:
                    k = k + 1
            pi[q] = k
    
        return pi
    
    
    if __name__ == '__main__':
        t = 'ABCDABDCABDEGF'
        p = 'ABD'
    
        print(patten_str(t, p))

结果

4

发表评论取消回复

表情：

评论列表（有 0 条评论，204人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python实现KMP算法字符串搜索

Python实现KMP算法字符串搜索 KMP算法是一种高效的字符串匹配算法，它的原理是在模式串与主串不同时，根据已匹配的字符前缀和后缀的最大匹配长度来移动模式串的位置，减少了

清疚/ 2024年03月23日 16:47/ 0 赞/ 65 阅读

相关字符串BF算法和KMP算法

什么是串数据结构中，字符串要单独用一种存储结构来存储，称为串存储结构。这里的串指的就是字符串。字符串通常是由零个或多个字符组成的有限序列。一般地，由n个字符串构成的

冷不防/ 2023年10月03日 14:06/ 0 赞/ 16 阅读

相关算法：字符串匹配算法：KMP算法

字符串匹配算法暴力算法BF算法，利用哈希值进行比较的RK算法，以及尽量减少比较次数的BM算法 ![在这里插入图片描述][20200301172159346.png]

小鱼儿/ 2023年07月10日 08:45/ 0 赞/ 23 阅读

相关高效字符串查找算法之KMP算法的java实现

源代码 public class KMP { public static void main(String[] args) {

╰半夏微凉°/ 2023年03月14日 10:44/ 0 赞/ 2 阅读

相关（Python）KMP算法匹配字符串

1 简介全称Knuth-Morris-Pratt算法，在[计算机科学][Link 1]中，Knuth-Morris-Pratt[字符串查找算法][Link 2]（简称为

柔情只为你懂/ 2023年02月27日 13:50/ 0 赞/ 34 阅读

相关字符串查找，KMP算法讲解

KMP 时间复杂度： O(n+m) 核心点；最长公共前后缀长度数组:next 若p\[i-1\]=p\[next\[i-1\]\],则 next\[i\] =

野性酷女/ 2023年01月02日 14:27/ 0 赞/ 247 阅读

相关算法——字符串匹配之KMP算法

前言前面博文分别介绍了字符串匹配算法《[朴素算法][Link 1]》、《[Rabin-Karp][][算法][Rabin-Karp]》和《[有限自动机算法][Link

柔光的暖阳◎/ 2022年08月13日 00:52/ 0 赞/ 215 阅读

相关 python算法-字符串查找KMP算法

问题：对于一个给定非空的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，

刺骨的言语ヽ痛彻心扉/ 2022年05月30日 22:10/ 0 赞/ 205 阅读

相关字符串KMP算法

可供参考： [http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html][http_www.cnbl

秒速五厘米/ 2021年09月14日 01:28/ 0 赞/ 401 阅读

相关字符串之KMP算法

一、介绍　　KMP算法全称Knuth-Morris-Pratt算法，是一种字符串匹配算法，常规字符匹配是每次移动一位，复杂度O(mn)；而KMP算法复杂度O(m+n)。

谁借莪１个温暖的怀抱￠/ 2021年09月11日 01:54/ 0 赞/ 405 阅读