python3 kmp 字符串匹配的方法-6ren

python3 kmp 字符串匹配的方法

转载作者：qq735679552 更新时间：2022-09-27 22:32:09

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章python3 kmp 字符串匹配的方法由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

先声明，本人菜鸟一个，写博客是为了记录学习的过程，以及自己的理解和心得，可能有的地方写的不好，希望大神指出。。.

抛出问题。

给定一个文本串test_str（被匹配的字符串）和模式串pat_str（需要从文本串中匹配的字符串），从文本串test_str中找出模式串pat_str第一次出现的位置，没有的话返回 -1 。

暴力方式。

在说kmp之前，我们先来讲下“暴力方式“，也就是说我们最原始的方法。　。

 
    ? 
   
         text_str  
         = 
         'asdabcdace' 
        
         pat_str  
         = 
         'abcdace' 
        
         def 
         str_match(text_str,pat_str): 
        
         for 
         i  
         in 
         range 
         ( 
         0 
         , 
         len 
         (text_str)): 
        
         j  
         = 
         1 
        
         while 
         j <  
         len 
         (pat_str): 
        
         if 
         text_str[i:i 
         + 
         j] ! 
         = 
         pat_str[ 
         0 
         :j]:  
         #从text_str第i个字符开始，看匹配是否成功 
        
         break  
         #匹配失败，直接跳出循环，i+1，继续从第一个字符匹配 
        
         j  
         + 
         = 
         1   
         #匹配成功就继续匹配下一个字符，知道pat_str每个字符都匹配完 
        
         if 
         j  
         = 
         = 
         len 
         (pat_str): 
        
         return 
         i 
        
         return 
         - 
         1 
        
         print 
         (str_match(text_str,pat_str))

之所以称之为暴力解法，就是因为每次匹配失败之后就将模式串，向后移动一位，从头开始匹配，一直循环下去。造成时间复杂度高，kmp也就是优化这个地方，每一次匹配失败，下次移动的距离next值。

python3 kmp 字符串匹配的方法

kmp 。

如果让我完全给你讲懂kmp算法可能不太容易，我只能大致粗略的将下它的一步步实现。我认为就一个重点，。

如何求出模式串每个字符对应的next值。

因为可能，每一次匹配失败的长度的字符不一样，也就对应每次移动的距离不一样，那我们如何求每个字符对应的next值，这就引出了另一个概念。

最大前缀和最大后缀。

　　　　 python3 kmp 字符串匹配的方法

假定最大前缀=最大后缀，长度为k 那么第i位字符，对应的next值就为k+1，一次循环就能求出每个字符的next值。

代码实现　　。

 
    ? 
   
         #求字符串的next值 
        
         text_str  
         = 
         'asdabcdace' 
        
         pat_str  
         = 
         'abcdace' 
        
         #得到字符对应的next值 
        
         def 
         str_next(s): 
        
         #前两个字符默认等于1 
        
         next 
         = 
         [ 
         1 
         , 
         1 
         ] 
        
         for 
         x  
         in 
         range 
         ( 
         2 
         , 
         len 
         (s)): 
        
         next 
         .append(str_max_prx(s,x, 
         next 
         [x 
         - 
         1 
         ] 
         - 
         1 
         )  
         + 
         1 
         ) 
        
         return 
         next 
        
         #参数 s字符串，匹配进行到的位置，下次开始匹配的位置 
        
         def 
         str_max_prx(s,x,last_value): 
        
         next 
         = 
         0 
        
         for 
         i  
         in 
         range 
         (last_value,x): 
        
         if 
         s[ 
         0 
         :i]  
         = 
         = 
         s[x 
         - 
         i:x]: 
        
         next 
         = 
         i 
        
         return 
         next 
        
         def 
         str_match(s,m): 
        
         next 
         = 
         str_next(s) 
        
         i 
         = 
         0 
        
         s_len  
         = 
         len 
         (s) 
        
         m_len  
         = 
         len 
         (m) 
        
         while 
         i < 
         = 
         m_len: 
        
         flag  
         = 
         true    
         #标志位，用来判断是否匹配成功 
        
         index  
         = 
         1 
        
         while 
         index < 
         = 
         s_len: 
        
         if 
         m[i:i  
         + 
         index] ! 
         = 
         s[ 
         0 
         :index]: 
        
         i  
         = 
         i  
         + 
         next 
         [index] 
        
         flag  
         = 
         false 
        
         break 
        
         else 
         : 
        
         index  
         + 
         = 
         1 
        
         if 
         flag: 
        
         break 
        
         if 
         i > 
         = 
         m_len: 
        
         i  
         = 
         - 
         1 
        
         return 
         i 
        
         res  
         = 
         str_match(pat_str,text_str) 
        
         print 
         (res)

代码就是这样，很多东西可能还需要自己理解。我记个笔记，为之后方便查找，希望对你能有帮助。也希望大家多多支持我.

原文链接：http://www.cnblogs.com/7749ha/p/9016246.html 。

最后此篇关于python3 kmp 字符串匹配的方法的文章就讲到这里了,如果你想了解更多关于python3 kmp 字符串匹配的方法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐：最强蜗牛贩卖机升级攻略最强蜗牛贩卖机升级方法

文章推荐： python如何通过实例方法名字调用方法

文章推荐：最强蜗牛金刚山怎么解锁最强蜗牛怎么开金刚山

文章推荐：详解Python最长公共子串和最长公共子序列的实现

awk - 如果行与“foo”匹配，线上方与“bar”匹配，线下方与“baz”匹配，则删除行？
使用sed和/或awk，仅在行包含字符串“ foo”并且行之前和之后的行分别包含字符串“ bar”和“ baz”时，我才希望删除行。因此，对于此输入： blah blah foo blah bar
c# - 如何按 X% 匹配 2 个字符串(即 >90% 匹配)
例如: S1: "some filename contains few words.txt" S2:“一些文件名包含几个单词 - draft.txt” S3:“一些文件名包含几个单词 - 另一个 dr
R 合并数据帧，允许不精确的 ID 匹配(例如，附加字符 1234 匹配 ab1234)
我正在尝试处理一些非常困惑的数据。我需要通过样本 ID 合并两个包含不同类型数据的大数据框。问题是一张表的样本 ID 有许多不同的格式，但大多数都包含用于匹配其 ID 中某处所需的 ID 字符串，例如
css - 匹配 col-md 时显示 div，匹配 col-sm 时不显示
我想在匹配特定屏幕尺寸时显示特定图像。在这种情况下，对于 Bootstrap ，我使用 col-xx-## 作为我的选择。但似乎它并没有真正按照我认为应该的方式工作。基本思路，我想显示一种全屏图像，
apache - mod_rewrite 问题 : RewriteCond %{REQUEST_FILENAME} ! -f 匹配，即使 REQUEST_FILENAME 不应(完全)匹配
出于某种原因，这条规则 RewriteCond %{REQUEST_FILENAME} !-f RewriteCond %{REQUEST_FILENAME} !-d RewriteRule ^(.*
F# 匹配 ->
我想做类似的东西(Nemerle 语法) def something = match(STT) | 1 with st= "Summ" | 2 with st= "AVG" =>
JavaScript 匹配
假设这是我的代码 var str="abc=1234587;abc=19855284;abc=1234587;abc=19855284;abc=1234587;abc=19855284;abc=123
JavaScript 匹配
我怎样才能得到这个字符串的数字:'(31.5393701, -82.46235569999999)' 我已经在尝试了，但这离解决方案还很远:) text.match(/$(\d+),(\d+)$/
JavaScript 匹配
如何去除输出中的逗号 (,)？有没有更好的方法从字符串或句子中搜索 url。 alert(" http://www.cnn.com df".match(/https?:\/\/([-\w\.]+
Python - 匹配
a = ('one', 'two') b = ('ten', 'ten') z = [('four', 'five', 'six'), ('one', 'two', 'twenty')] 我正在尝试
vba - 循环遍历行和列时的索引/匹配
我已经编写了以下代码，我希望用它来查找从第 21 列到另一张表中最后一行的值，并根据这张表中 A 列和另一张表中 B 列中的值将它们返回到这张表床单。当我使用下面的代码时，我得到一个工作表错误。你能
Excel 匹配 IF 语句未正确评估
我在以下结构中有两列 A B 1 49 4922039670 我已经能够评估 =LEN(A1)如2 , =LEFT(B1,2)如49 , 和 =LEFT(B1,LEN(A1)
基于行首的 Vim 匹配
我有一个文件，其中一行可以以 + 开头, -或 * .在其中一些行之间可以有以字母或数字(一般文本)开头的行(也包含这些字符，但不在第 1 列中!)。知道这一点，设置匹配和突出显示机制的最简单方法是
正则表达式:匹配，但如果在评论中则不匹配
我有一个数据字段文件，其中可能包含注释，如下所示: id, data, data, data 101 a, b, c 102 d, e, f 103 g, h, i // has to do with
匹配 url 的正则表达式模式
我有以下模式:/^\/(?P.+)$/匹配:/url . 我的问题是它也匹配 /url/page ，如何忽略/在这个正则表达式中？该模式应该: 模式匹配:/url 模式不匹配:/url/page 提
r - R中多维度的聚类/匹配
我有一个非常庞大且复杂的数据集，其中包含许多对公司的观察。公司的一些观察是多余的，我需要制作一个键来将多余的观察映射到一个单独的观察。然而，判断他们是否真的代表同一家公司的唯一方法是通过各种变量的相似
xpath 匹配 - 查找值不在值集中的标签是否存在
我有以下 XML A B C 我想查找 if not(exists(//Record/subRecord
javascript - 匹配/不匹配的正则表达式上没有出现警报框？
我制作了一个正则表达式来验证潜在的比特币地址，现在当我单击报价按钮时，我希望根据正则表达式检查表单中输入的值，但它不起作用。 https://jsfiddle.net/arkqdc8a/5/ var
sql - 检查支架是否平衡/匹配
我有一些 MS Word 文档，我已将其全部内容转移到 SQL 表中。内容包含多个方括号和大括号，例如 [{a} as at [b],] {c,} {d,} etc 我需要进行检查以确保括号平衡/匹
JavaScript Unicode 匹配
我正在使用 Node.js 从 XML 文件读取数据。但是当我尝试将文件中的数据与文字进行比较时，它不匹配，即使它看起来相同: const parser: xml2js.Parser = new

qq735679552

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

python3 kmp 字符串匹配的方法