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

刺骨的言语ヽ痛彻心扉 2022-05-30 22:10 206阅读 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 条评论，206人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关【Python】KMP算法

文章目录字符串查找问题暴力求解算法 Python代码 KMP算法 next的递推关系

淩亂°似流年/ 2022年05月22日 03:59/ 0 赞/ 212 阅读

相关字符串匹配算法KMP

KMP算法的原理，这里我不写，建议参考： [http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80

╰+攻爆jí腚メ/ 2022年01月14日 00:41/ 0 赞/ 382 阅读

相关字符串KMP算法

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

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

相关字符串之KMP算法

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

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