数据结构 字符串匹配

欢迎点击「算法与编程之美」关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

问题描述

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

解决方案

字符串匹配问题可以归纳为如下的问题：在长度为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)从左到右逐个字符匹配;（2）发现不匹配时，转去考虑目标串里的下一个位置是否与模式串匹配。

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

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

二．无回溯串匹配算法（KMP算法）

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

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

结语

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