详解KMP算法以及python如何实现

算法思路

Knuth-Morris-Pratt（KMP）算法是解决字符串匹配问题的经典算法，下面通过一个例子来演示一下：

给定字符串"BBC ABCDAB ABCDABCDABDE"，检查里面是否包含另一个字符串"ABCDABD"。

1.从头开始依次匹配字符，如果不匹配就跳到下一个字符

2.直到发现匹配字符，然后经过一个内循环严查字符串是否匹配

3.发现最后一个D不匹配，下面就该思考应该把字符串向右移动多少个位置呢？传统做法可能是移动一格，KMP算法就创新在这里。KMP算法通过查询一个Partial Match Table（表内存有字符串信息），然后计算出需要移动的步数，这个表后面会介绍怎么来的。

这里我们看到D前面是B，查表得到第二个B对应的是2，所以 移动数 = 已匹配字符数 - 查表所得数 也就是 6 - 2 = 4， 需要向右移动四格。

下面也是重复这个步骤

直到发现匹配或者字符长度超出（未发现匹配）。

Partial Match Table

那么这个查询的表是怎么来的呢？仍然以"ABCDABD"为例

－　"A"的前缀和后缀都为空集，共有元素的长度为0；

－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

python实现

def partial_table(p):
  '''''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''
  prefix = set()
  res = [0]
  for i in range(1, len(p)):
    prefix.add(p[:i])
    postfix = {p[j:i + 1] for j in range(1, i + 1)}
    #print(p[:i+1],prefix,postfix,prefix & postfix or {''})
    res.append(len((prefix & postfix or {''}).pop()))
  return res

def kmp_match(s, p):
  m = len(s);
  n = len(p)
  cur = 0 # 起始指针cur
  table = partial_table(p)
  while cur <= m - n:   #只去匹配前m-n个
    for i in range(n):
      if s[i + cur] != p[i]:
        cur += max(i - table[i - 1], 1) # 有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位
        break
    else:
      return True # loop从 break 中退出时，else 部分不执行。
  return False

print partial_table1("ABCDABD")
print kmp_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")

以上就是详解KMP算法以及python如何实现的详细内容，更多关于python实现KMP算法的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • python实现kmp算法的实例代码

    kmp算法 kmp算法用于字符串的模式匹配,也就是找到模式字符串在目标字符串的第一次出现的位置 比如 abababc 那么bab在其位置1处,bc在其位置5处 我们首先想到的最简单的办法就是蛮力的一个字符一个字符的匹配,但那样的时间复杂度会是O(m*n) kmp算法保证了时间复杂度为O(m+n) 基本原理 举个例子: 发现x与c不同后,进行移动 a与x不同,再次移动 此时比较到了c与y, 于是下一步移动成了下面这样 这一次的移动与前两次的移动不同,之前每次比较到上面长字符串的字符位置后,直接把模

  • Python实现字符串匹配的KMP算法

    kmp算法 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特--莫里斯--普拉特操作(简称KMP算法).KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的.具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息. #! /usr/bin/python # coding=utf-8 """ 基于这篇文章的python实现 http://bl

  • 详解小白之KMP算法及python实现

    在看子串匹配问题的时候,书上的关于KMP的算法的介绍总是理解不了.看了一遍代码总是很快的忘掉,后来决定好好分解一下KMP算法,算是给自己加深印象. 在将KMP字串匹配问题的时候,我们先来回顾一下字串匹配的暴力解法: 假设字符串str为: "abcgbabcdh",  字串substr为: "abcd" 从第一个字符开始比较,显然两个字符串的第一个字符相等('a'=='a'),然后比较第二个字符也相等('b'=='b'),继续下去,我们发现第4个字符不相等了('g'!

  • KMP算法精解及其Python版的代码示例

    KMP算法是经典的字符串匹配算法,解决从字符串S,查找模式字符串M的问题.算法名称来源于发明者Knuth,Morris,Pratt. 假定从字符串S中查找M,S的长度ls,M的长度lm,且(ls > lm). 朴素的字符串查找方法 从字符串S的第一个字符开始与M进行比较,如果匹配失败.从下一字符开始,重新比较.指导第 (ls - lm) 个字符. 这种方法容易想到并且容易理解,效率不高. 问题在于每次匹配失败后,移动的步伐固定为 1,其实步子可以迈得再大一些. KMP的字符串查找方法 假定在模式

  • python实现的二叉树算法和kmp算法实例

    主要是:前序遍历.中序遍历.后序遍历.层级遍历.非递归前序遍历.非递归中序遍历.非递归后序遍历 复制代码 代码如下: #!/usr/bin/env python#-*- coding:utf8 -*- class TreeNode(object):    def __init__(self, data=None, left=None, right=None):        self.data = data        self.left = left        self.right =

  • Python字符串匹配算法KMP实例

    本文实例讲述了Python字符串匹配算法KMP.分享给大家供大家参考.具体如下: #!/usr/bin/env python #encoding:utf8 def next(pattern): p_len = len(pattern) pos = [-1]*p_len j = -1 for i in range(1, p_len): while j > -1 and pattern[j+1] != pattern[i]: j = pos[j] if pattern[j+1] == pattern

  • 详解KMP算法以及python如何实现

    算法思路 Knuth-Morris-Pratt(KMP)算法是解决字符串匹配问题的经典算法,下面通过一个例子来演示一下: 给定字符串"BBC ABCDAB ABCDABCDABDE",检查里面是否包含另一个字符串"ABCDABD". 1.从头开始依次匹配字符,如果不匹配就跳到下一个字符 2.直到发现匹配字符,然后经过一个内循环严查字符串是否匹配 3.发现最后一个D不匹配,下面就该思考应该把字符串向右移动多少个位置呢?传统做法可能是移动一格,KMP算法就创新在这里.K

  • 详解K-means算法在Python中的实现

    详解K-means算法在Python中的实现

    K-means算法简介 K-means是机器学习中一个比较常用的算法,属于无监督学习算法,其常被用于数据的聚类,只需为它指定簇的数量即可自动将数据聚合到多类中,相同簇中的数据相似度较高,不同簇中数据相似度较低. K-MEANS算法是输入聚类个数k,以及包含 n个数据对象的数据库,输出满足方差最小标准k个聚类的一种算法.k-means 算法接受输入量 k :然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高:而不同聚类中的对象相似度较小. 核心思想 通过迭代寻找

  • python实现连续变量最优分箱详解--CART算法

    关于变量分箱主要分为两大类:有监督型和无监督型 对应的分箱方法: A. 无监督:(1) 等宽 (2) 等频 (3) 聚类 B. 有监督:(1) 卡方分箱法(ChiMerge) (2) ID3.C4.5.CART等单变量决策树算法 (3) 信用评分建模的IV最大化分箱 等 本篇使用python,基于CART算法对连续变量进行最优分箱 由于CART是决策树分类算法,所以相当于是单变量决策树分类. 简单介绍下理论: CART是二叉树,每次仅进行二元分类,对于连续性变量,方法是依次计算相邻两元素值的中位

  • 详解Bagging算法的原理及Python实现

    详解Bagging算法的原理及Python实现

    目录 一.什么是集成学习 二.Bagging算法 三.Bagging用于分类 四.Bagging用于回归 一.什么是集成学习 集成学习是一种技术框架,它本身不是一个单独的机器学习算法,而是通过构建并结合多个机器学习器来完成学习任务,一般结构是:先产生一组"个体学习器",再用某种策略将它们结合起来,目前,有三种常见的集成学习框架(策略):bagging,boosting和stacking 也就是说,集成学习有两个主要的问题需要解决,第一是如何得到若干个个体学习器,第二是如何选择一种结合策

  • rsa详解及例题及python算法

    rsa详解及例题及python算法

    目录 rsa 详解及例题及python 算法原理 算法描述 案例手稿 实现python 运算 m=71 -> c=15 c=15 -> m=71 正常的rsa c->m m->c 安全性 运算速度 rsa 详解及例题及python 算法原理 RSA公开密钥密码体制的原理是:根据数论,寻求两个大素数比较简单,而将它们的乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥 算法描述 任意选取两个不同的大素数p和q计算乘积 n=pq n 的欧拉函数 φ(n): φ(n)=(p-1)

  • 图文详解感知机算法原理及Python实现

    图文详解感知机算法原理及Python实现

    目录 写在前面 1.什么是线性模型 2.感知机概述 3.手推感知机原理 4.Python实现 4.1 创建感知机类 4.2 更新权重与偏置 4.3 判断误分类点 4.4 训练感知机 4.5 动图可视化 5.总结 写在前面 机器学习强基计划聚焦深度和广度,加深对机器学习模型的理解与应用.“深”在详细推导算法模型背后的数学原理:“广”在分析多个机器学习模型:决策树.支持向量机.贝叶斯与马尔科夫决策.强化学习等. 本期目标:实现这样一个效果 1.什么是线性模型 线性模型的假设形式是属性权重.偏置与属性

  • 详解Dijkstra算法之最短路径问题

    详解Dijkstra算法之最短路径问题

    一.最短路径问题介绍 问题解释: 从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径 解决问题的算法: 迪杰斯特拉算法(Dijkstra算法) 弗洛伊德算法(Floyd算法) SPFA算法 这篇博客,我们就对Dijkstra算法来做一个详细的介绍 二.Dijkstra算法介绍 2.1.算法特点 迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树.该算法常用于路由算法或者作为其他图算法的一个子模块. 2.2.算法的

  • 详解Dijkstra算法原理及其C++实现

    详解Dijkstra算法原理及其C++实现

    目录 什么是最短路径问题 Dijkstra算法 实现思路 案例分析 代码实现 什么是最短路径问题 如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小. 单源最短路径问题是指对于给定的图G=(V,E),求源点v0到其它顶点vt的最短路径. Dijkstra算法 Dijkstra算法用于计算一个节点到其他节点的最短路径.Dijkstra是一种按路径长度递增的顺序逐步产生最短路径的方法,是一种贪婪算法. Dijkstra算法

  • C++示例详解Prim算法与优先队列

    C++示例详解Prim算法与优先队列

    目录 Prim算法 prim代码实现 优先队列 优先队列代码实现 自定义类型优先序列 贪心算法的本质是:一个问题的局部最优解,也是该问题的全局最优解. 最小生成树的最优子结构性质:假设一个无向图包含两部分A,B,其中A为最小生成树部分,B为剩余部分,则存在以下性质:该无向图中一个顶点在A部分,另一个顶点在B部分的边中,权值最小的边一定属于整个无向图的最小生成树,即部分最小权值是整个最小生成树的局部最有解,该性质符合贪心算法的特点. Prim算法 基于最小生成树的该性质,使用prim算法来求解最小

随机推荐