算法 | 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 团队