【算法笔记】字符串匹配

BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法：

主串和模式串：

在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m

我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

BF 算法的时间复杂度是 O(n*m)

等价于

比如匹配Google 和Goo 是最好时间复杂度，匹配Google 和ble是匹配失败的最好时间复杂度。

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特—莫里斯—普拉特算法。KMP算法主要分为两个步骤：字符串的自我匹配，目标串和模式串之间的匹配。

看来网上很多的文章，感觉很多的都没有说清楚，这里直接复制阮一峰的内容，讲的很清晰

内容来自 http://www.ruanyifeng.com/blog/

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

因为B与A不匹配，搜索词再往后移。

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

接着比较字符串和搜索词的下一个字符，还是相同。

直到字符串有一个字符，与搜索词对应的字符不相同为止。

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"宽碰耐。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

因为 6 - 2 等于4，所以将吵搭搜索词向后移动4位。

因为空格与C不匹配，搜索词还要继续往后移慎春。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

因为空格与A不匹配，继续后移一位。

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP 算法的 3 到 4 倍。

BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）

未完待续

参考文章：

字符串匹配的Boyer-Moore算法

KMP算法也是比较著名的模式匹配算法。是由灶正 D.E.Knuth,J.H.Morrs 和 VR.Pratt 发表的一个模式匹配算法。可以大大避免重复遍历的情况。

如果使用暴风算法的话，前面五个字母完全相等，直到第六个字母 "f" 和 "x" 不相等。如下图：

T = “abcdex”

j123456

模式串 abcdex

next[j] 011111

T = "abcabx"

j 123456

模式串T abcabx

next[j]011123

T = "ababaaaba"

j———————123456789

模式串T——— ababaaaba

next[j]————011234223

T = "aaaaaaaab"

j——毕辩简—————123456789

模式串T——— aaaaaaaab

next[j]————012345678

next数组其实就是求解字符串要回溯的位置

假设，主串S= “abcababca”模式串T=“abcdex”，由以上分析得出next数组为011111，next数组意味着当主串与模式串不匹配时，都需要从第一个的位置重新比较。

KMP算法也是有缺陷的，比如主串S=“aaaabcde”,模式串T= “aaaaax”。next的数组就是012345；

当开始匹配时，当i= 5，j = 5时，我们发现字符"b"与字符“a”不相等，如上图，j = next[5] = 4

由于T串的第二、三、四、五位置的字符都与首位“a”相等，那么可以用首位next[1]的值去取代与它相等的手裤后续字符的next[j],那么next数组为{0,0,0,0,0,5}

在求解nextVal数组的5种情况

1. re.match 尝试从字符串的起始位置匹配一个模式，如果不是起始位置匹李蚂配成功的话，match()就返回none。

import re

line="this hdr-biz 123 model server 456"

pattern=r"123"

matchObj = re.match( pattern, line)

2. re.search 扫描整个字符串并返回第一个成功的匹配。

import re

line="this hdr-biz model server"

pattern=r"hdr-biz"

m = re.search(pattern, line)

3. Python 的re模块提供了re.sub用于替换字符串中的匹配项。

import re

line="this hdr-biz model args= server"

patt=r'args='

name = re.sub(patt, "", line)

4. compile 函数用于编译正则表达式，生成一个正则表达式( Pattern )对象，供 match() 和 search() 这两个函数使用。

import re

pattern = re.compile(r'\d+')

5. re.findall 在字符串中找到正则表达式所匹配的所有子串，并返回一个列表睁链，如果没有找到匹配的，则返回空列表。

import re

line="this hdr-biz model args= server"

patt=r'server'

pattern = re.compile(patt)

result = pattern.findall(line)

6. re.finditer 和 findall 类似，在字符串中找到正则表达式所匹配的所有子串，并把它们作为一个迭代器返回。

import re

it = re.finditer(r"\d+","12a32bc43jf3")

for match in it:

print (match.group() )

关于Python字符串匹配6种方法的使用，青藤小编就和您分享到这里了。如果您对python编程有浓厚的兴趣，希望这篇文章可以为您提供帮助。如果您还想了解更多关于python编程的技巧及素材等内容，可以点击本站悉扰孙的其他文章进行学习。

以上是小编为大家分享的关于Python字符串匹配6种方法的使用的相关内容，更多信息可以关注环球青藤分享更多干货

---