算法 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个字符都与目标串对应字符相同,找到了一个匹配。继续做下去还可能找到更多匹配。

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

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

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

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

3. 结语

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

where2go 团队

微信号:算法与编程之美

一个专注于分享算法思想的公众号!

温馨提示:点击页面下方“留言”发表评论,期待您的参与!期待您的转发!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190914A0EUBX00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券