专栏首页算法与编程之美算法 | KMP字符串匹配

算法 | KMP字符串匹配

1. 问题描述

Python字符串str是在Python编写程序过程中,最常见的一种基本数据类型。字符串是许多单个子串组成的序列,其主要是用来表示文本。字符串是不可变数据类型,也就是说你要改变原字符串内的元素,只能是新建另一个字符串。字符串匹配就是基于最简单的字符比较,其中的模式串就是普通字符串,所做匹配是在目标串里查找等于模式串的子串。也就是说,比较的一方是表示模式的字符串,另一方是目标字符串的所有可能子串。我们常用的就是朴素的串匹配算法和无回溯串匹配算法(KMP算法)。

2. 问题分析

字符串匹配问题可以归纳为如下的问题:在长度为n的文本T[1...n]中,查找一个长度为m的模式P[1...m]。并且假设T,P中的元素都来自一个有限字母集合Ʃ。如果存在位移s,其中0≤s≤n-m,使得T[s+1..s+m]= P[1..m]。则可以认为模式P在T中出现过。

(1) 朴素的串匹配算法

最简单的朴素匹配算法采用最直观可行的策略: (1)从左到右逐个字符匹配;(2)发现不匹配时,转去考虑目标串里的下一个位置是否与模式串匹配。

如下图所示:上面的长串是目标串,下面是模式串。在初始状态(1)两个串的起始字符对齐。顺序比较,立即发现第一对字符不同。将模式串右移一位得到(2)。顺序比较第一对字符相同,但第二对字符不同。将模式串再右移一位。这样继续到状态(4),模式串的5个字符都与目标串对应字符相同,找到了一个匹配。继续做下去还可能找到更多匹配。

下面是朴素串匹配算法的一个实现:

def naive_string_match(T, P): n = len(T) m = len(P) for s in range(0, n-m+1): k = 0 for i in range(0, m): if T[s+i] != P[i]: break else: k += 1 if k == m: print s

(2) 无回溯串匹配算法(KMP算法)

在状态(0)匹配到第一个c失败时,由于已知前两个字符不同,KMP算法直接把模式串移两个位置,模式串开头的a移到c匹配失败的位置,达到状态(1)。这次匹配直到模式申最后的C处失败,由于已知模式串c之前是a,首字符也是a,而且两个字符之间的字符与它们不同,不可能有匹配。KMP算法直接把模式串的b移到刚才匹配c失败的位置(前面字符a肯定匹配,不必再试),达到状态(2)。接下去从模式串的b继续匹配,找到了一个成功匹配。在这个过程中未出现重新检查目标串前面字符的情况(无回溯)。

下面是无回溯匹配算法的一个实现:

def kmp_matcher(T, P): T = ' ' + T P = ' ' + Pn = len(T) – 1 m = len(P) – 1 t = KMP.longest_prefix_suffix(P) q = 0for i in range(1, n+1):while q > 0 and P[q+1] != T[i]:q = t[q] if P[q+1] == T[i]: q += 1 if q == m: print i-m+1q = 0

3. 结语

字符串匹配处理的关键就是字符处理后的栈是否为空。当所有字符处理完成后,栈为空则字符串匹配成功。反之若栈不为空,则表示字符串匹配失败。

where2go 团队


本文分享自微信公众号 - 算法与编程之美(algo_coding),作者:马原涛

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构|字符串匹配

    python字符串str是在Python编写程序过程中,最常见的一种基本数据类型。字符串是许多单个子串组成的序列,其主要是用来表示文本。字符串是不可变数据类型,...

    算法与编程之美
  • 算法字符串匹配(查找)-BF算法

    字符串是数据结构中比较简单的一种,但又是我们最常用的数据结构之一。对于字符串对象,最重要的操作之一便是字符串匹配(查找),本篇文章便向大家介绍一个典型的匹配算法...

    算法与编程之美
  • 微信小程序|Tab标签页

    在使用小程序的时候会看到大多数都是在小程序的底部设置导航栏,然而会发现有一些小程序的顶部也会有导航栏,那么如何来设置小程序的Tab标签页呢?

    算法与编程之美
  • 漫画:探索字符串匹配系列 第一讲(Sunday 是个啥玩意)

    今天是小浩算法“365刷题计划”第84天 。前几天的内容大家可能会觉得比较散。这是因为我目前正在筹划背包系列和贪心系列两个主题的内容,所以时间比较紧张,就拿出了...

    程序员小浩
  • 刨根究底正则表达式之二——正则表达式基础

    虽然本系列文章开篇会简单介绍正则表达式的一些基础知识,但主要限于本系列文章所想强调的要点,因此本系列文章并不适合用于入门。

    用户1876609
  • 第31天:面试比 KMP 还容易被问到的匹配算法!

    当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

    程序员小浩
  • 策略模式(Strategy)

    Java高级架构
  • IC 圆桌派第七日复盘:汽车电子,航载

    IC 圆桌派第七日主题是:『效率,研发管理,编程』关于这部分内容,高老师是专家,等她的专业复盘。老驴今天复盘第七日讨论过的技术问题,涵盖汽车电子,FPGA, ...

    老秃胖驴
  • MMD_5b_ComputationalAdvertising

    OnlineAlgorithms 与Offline算法的对比 BipartiteMatching 例子 问题描述 一般用于Online场合 贪心算法 描述 算法...

    用户1147754
  • 如何选择Spark机器学习API

    译者注:本文简要介绍了四种经典的机器学习算法。 本文将简要介绍Spark机器学习库(Spark MLlib’s APIs)的各种机器学习算法,主要包括:统计算法...

    CSDN技术头条

扫码关注云+社区

领取腾讯云代金券