字符串匹配的算法（图示代码一看就懂的字符串匹配算法KMP）

字符串匹配的算法（图示代码一看就懂的字符串匹配算法KMP）待匹配字符 P：mnmno给定字符串 S：mnmmomnmnomo全文共1839字，预计阅读时间20分钟。字符串模式匹配是NLP领域的基础任务，可以在大量的文本内容中快速找到需要的文本信息，比如在文章中搜索关键词的位置和数量，在现实生活中有较高的使用频率，本文主要介绍几种常见的字符串模式匹配算法：KMP，BM和Sunday。1. KMP （Kunth-Morris-Pratt-string-searching algorithm）

数据与智能 本公众号关注大数据与人工智能技术。由一批具备多年实战经验的技术极客参与运营管理，持续输出大数据、数据分析、推荐系统、机器学习、人工智能等方向的原创文章，每周至少输出7篇精品原创。同时，我们会关注和分享大数据与人工智能行业动态。欢迎关注。

作者 | yu

校对 | gongyouliu

编辑 | auroral-L

全文共1839字，预计阅读时间20分钟。

字符串模式匹配是NLP领域的基础任务，可以在大量的文本内容中快速找到需要的文本信息，比如在文章中搜索关键词的位置和数量，在现实生活中有较高的使用频率，本文主要介绍几种常见的字符串模式匹配算法：KMP，BM和Sunday。

1. KMP （Kunth-Morris-Pratt-string-searching algorithm）

给定字符串 S：mnmmomnmnomo

待匹配字符 P：mnmno

步骤

1）. 待匹配字符 P的前缀表（prefix table）的生成

step 1 写出该字符串所有的前缀

m

m n

m n m

m n m n

m n m n o

step 2 对于每一个字符串 找出其最长公共前缀后缀长度 注：公共前缀后缀长度小于原始字符串长度

字符串	最长公共前缀后缀长度
''	-1
m	0
m n	0
m n m	1 前缀（m） 后缀（m）
m n m n	2 前缀（m n） 后缀（m n）
m n m n o	0

得到到前缀表 （注：最长公共前缀后缀长度右移一位）

m	n	m	n	o
-1	0	0	1	2	0

2）字符串匹配

step 1 将字符串S，P头部对齐，从左到右依次比较字符

step 2 遇到不同的字符时，获取字符串P对应最长公共前后缀的长度，找到其对应的索引值，将字符串P的索引值与字符串S失配位置对齐，从未匹配位置开始从左到右依次比较。若字符串P对应的索引值为-1，则将字符串P右移一位，比较字符。

step 3 重复step 2 ，直到匹配成功

匹配成功，找到第一个匹配位置！

step 4 若想找到S串中全部的P串则继续重复step2

code

def genPreTable(P): ''' :param P: :return: 前缀表 ''' preTable = [-1] * (len(P) 1) if len(P) > 1: preTable[1] = 0 i j = 0 1 while j < len(P): if i == -1 or P[i] == P[j]: i = 1 j = 1 preTable[j] = i else: i = preTable[i] return preTable def kmp(S P): ''' :param S: :param P: :return: 返回所有匹配成功的index ''' indices = [] if not P: return [0] preTable = genPreTable(P) s = p = 0 while s < len(S): if p == -1 or S[s] == P[p]: s = 1 p = 1 else: p = preTable[p] if p == len(P): indices.append(s - p) p = preTable[p] return indices S = 'mnmmomnmnomo' P = 'mnmno' result = kmp(S P) print(result)

2. BM （Boyer-Moore）

给定字符串 S：mnommnomn

待匹配字符 P：mnomn

（注：从右向左匹配字符串）

1）坏字符规则 （bad character Heuristics）

字符串S跟字符串P中某个字符不匹配时，称S中的这个失配字符为坏字符，此时P需右移。

右移位数 = 坏字符对应P中的位置 - 坏字符在P中最右出现的位置。若P中不存在坏字符，则最右出现位置置-1。

上图所示字符串S，P头部对齐。从右向左比较字符，若字符不同，则右移字符串P，使P中右侧第一个字符‘m‘与S中失配的'm'对齐（字符串P右移一位）

2） 好后缀规则（Good-Suffix Heuristics）

字符失配时，右移位数 = 好后缀在P中的索引 - 好后缀在P上一次出现的索引。若好后缀在模式串中没有再次出现，则为-1。

如上图所示，好后缀为mn， 字符串P右移3位（如下图所示）

步骤

step1. 字符串S，P头部对齐。

step2. 从右到左比较字符，根据上述规则分别计算移动距离，选择较大的距离进行移动，直至匹配成功。

code

def getBadChar(P): ''' :param P: :return: 坏字符表 ''' badChar = {} for i in range(len(P) - 1): char = P[i] badChar[char] = i 1 return badChar def getGoodSuffix(P): # 预生成好后缀表 goodSuffix = {} goodSuffix[''] = 0 for i in range(len(P)): subString = P[len(P) - i - 1:] for j in range(len(P) - i - 1): if subString == P[j:j i 1]: goodSuffix[subString] = len(P) - j - i - 1 return goodSuffix def BM(S P): ''' :param S: :param P: :return: 返回所有匹配成功的index ''' p s = len(P) len(S) if not P: return [0] i j = 0 p indices = [] badChar = getBadChar(P) goodSuffix = getGoodSuffix(P) while i < s: while (j > 0): if i j > s: return indices strOfS = S[i j - 1:i p] strOfP = P[j - 1:] if strOfS == strOfP: j = j - 1 else: i = i max(goodSuffix.setdefault(strOfP[1:] p) j - badChar.setdefault(S[i j - 1] 0)) j = p if j == 0: indices.append(i) i = 1 j = len(P) return indices S = "mnommnomn" P = "mnomn" result = BM(S P) print(result)

3. Sunday

给定字符串 S：mnommpomnomn

待匹配字符 P：mnomn

步骤

step1. 字符串S，P头部对齐。

step2. 从左到右比较字符，在匹配失败时获取字符串S中失败字符的下一位字符，在字符串P中获取该字符。若该字符没有在P中出现则对应的移动位数 = P的长度 1；否则，移动位数 = P的长度 - 该字符在P中最右出现的索引 。

code

def move(P p char): index = p 1 if char not in P: return index for i in range(p): if P[i] == char: index = p - i return index def sunday(S P): if not P: return [0] p s = len(P) len(S) temp_index = 0 indices = [] while temp_index p <= s: p_head_index = 0 s_head_index = temp_index print(s_head_index p_head_index) while s_head_index < s and p_head_index < p and S[s_head_index] == P[p_head_index]: s_head_index = 1 p_head_index = 1 if p_head_index == p: indices.append(temp_index) temp_index = 1 if temp_index p >= s: break temp_index = move(P p S[temp_index p]) return indices S = "mnommpomnomn" P = "mnomn" result = sunday(S P) print(result)