符串匹配算-几种常见的概念粗讲
Author：zhoulujun Date：
朴素的模式匹配算法
假设我们要从主串s="goodgoogle"找到t="google"这个子串的位置，我们需要下列步骤
1、主串s的第1位开始，s与t前三个字符都匹配成功，第四个字符不匹配（竖线表示相等，闪电状弯折表示不想等）
2、主串s的第2位开始，匹配失败
3、主串s的第3位开始，匹配失败
4、主串s的第4位开始，匹配失败
5、主串s的第5位开始，s与t，6个字符全部匹配成功
对主串的每一个字符作子串开头，要与匹配的字符串进行匹配。对主串作大循环，每一个字符开头作t长度的小循环，直到匹配成功或者全部遍历完为止。
朴素算法复杂度：
最好的情况，时间复杂度为O(1)。比如在"googlegood"中找"google"，
稍差一点，时间复杂度O(n+m)。比如"abcdefgoogle"中找"google"，其中n为主串长度，m为子串长度，根据等概率原则，平均（n+m）次查找，时间复杂度为O(n+m)
最坏的情况，时间复杂度为O((n-m+1)*m)。每次不成功都发生在串t的最后一个字符，比如子串t="0000000001"，9个"0"和一个"1"。主串s="00000000000000000000000000000000000000000000000001"，49个"0"和一个"1"
Rabin-Karp算法
Rabin-Karp字符串匹配算法和前面介绍的朴素算法类似，也是对应每一个字符进行比较，不同的是Rabin-Karp采用了把字符进行预处理，也就是使用hash函数分别对输入串的子串和模式串分别hash，然后比较。预处理复杂度是 O(m)，匹配时间复杂度为 O((n - m + 1) * m)，既然与朴素算法的匹配时间一样，而且还多了一些预处理时间，那为什么我们还要学习这个算法呢？
虽然Rain-Karp在最坏的情况下与朴素的世间复杂度一样，但是实际应用中往往比朴素算法快很多。而且该算法的 期望匹配时间是O(n + m)(参照《算法导论》)
在朴素算法中，我们需要挨个比较所有字符，才知道目标字符串中是否包含子串。为了避免挨个字符对目标字符串和子串进行比较，Rabin-Karp算法会先尝试一下二者的hash值判断二者是否相等，可以显著提升效率
Rabin-Karp算法的思想：
假设模式串的长度为m,目标字符串的长度为n（n > m）
计算模式串的hash值
计算目标字符串中每个长度为m的子串的hash值（共需要计算N-M+1次）
比较hash值
如果hash值不同，字符串必然不匹配，如果hash值相同，还需要使用朴素算法再次判断来排除hash冲突的干扰
为了快速的计算出目标字符串中每一个子串的hash值，Rabin-Karp算法并不是对目标字符串的 每一个长度为m的子串都重新计算hash值，而是在前几个字串的基础之上， 计算下一个子串的hash值，这就加快了hash之的计算速度，将朴素算法中的内循环的世间复杂度从O(m)将到了O(1)。
KMP模式匹配算法
假设主串s="abcdefgab"，t="abcdex"
"abcdex"的首字符"a"与后面的串"bcdex"中任何一个字符都不相等，子串t与主串s的前5个字符分别相等，意味着子串t的首字符"a"不可能与s串的第2位到第5位的字符相等
上面的案例，子串t中没有重复的字符，下面给出一个有重复字符的例子
假设s="abcababca"，t="abcabx"
第一步，前5个字符相等，第6个字符不相等，根据前面的经验，t的首字符"a"与t中第二位、第三位字符军部等，不需要判断
子串t中第1位与第4位相等，第2位与第5位相等；主串s中第4位，第5位分别与子串t中第4位，第5位相等，意味着子串的第1位与第2位分别与主串第4位与第5位相等，不需要判断
总结：i值不回溯，j值的变化只与子串有关，取决于t串中的结构中是否有重复的字符串。
我们把t串各个位置的变化定义为一个数组next，next的长度就是t串的长度
举例说明next数组：
BM算法
BM算法相对经典的KMP字符串匹配算法，效率更好。在模式串长度大的时候效率更高。算法需要对模式串进行预处理，处理过后，在搜索过程中就可以最大减少字符比较次数，以此提高效率。BM算法主要三个特点：从模式串最右开始进行匹配；坏字符表；好后缀表。基本思路就是从右往左进行字符匹配，遇到不匹配的字符后从坏字符表和好后缀表找一个最大的右移值，将模式串右移继续匹配。
算法分为两个阶段：预处理阶段和搜索阶段。
预处理阶段时间复杂度空间复杂度均为O(m + σ)。m是模式长度，σ是字符集大小，一般考虑为单字节8位共256种。
搜索阶段时间复杂度O(m * n)。
当模式串是非周期性的，最坏情况下需要做3n次字符比较，n是文本长度。
最好情况下性能为O(n / m)
坏字符算法：
不匹配的字符被称为坏字符，当字符不匹配时，遇到坏字符的后移次数为坏字符在模式串里的位置减去模式串中上一次在模式串中出现的位置，由两种情况汇总得到：
若不匹配的字符不存在于模式串内，那么直接将模式串移动到该字符后
不匹配的字符存在于模式串内，那么后移模式串，直到模式串的某个字符与该字符匹配
好后缀规则：
连续可以匹配的后缀被成为好后缀，当好后缀存在，移动次数为好后缀的位置减去模式串中上一次好后缀的位置。
# Strings s1, s2 # s1: input string, length = n # s2: pattern, length = m # 这里这个 256 这个 magic number 是字符的最大数量 # bm_bad_ch 为字符字模式串中的最右边的位置 bm_bad_ch = [m for i in range(256)]for i in range(m): bm_bad_ch[ord(s2[i])] = i # suffix[i] 为以 i 为边界，可以与模式串后缀匹配的最大长度 suffix = [0 for i in range(m)]suffix[m - 1] = mfor i in range(m - 2, -1, -1): k = i while k >= 0 and s2[k] == s2[m - 1 - i + k]: k -= 1 suffix[i] = i - k # 对于没有匹配到的情况 bm_good_suffix = [m for i in range(m)]j = 0for i in range(m - 1, -1, -1): if suffix[i] == i + 1: # 后缀没有完全匹配，找到一个最大前缀 while j < m - 1 - i: if bm_good_suffix[j] == m: bm_good_suffix[j] = m - 1 - i j += 1# 对于直接能匹配好后缀的情况for i in range(m - 1): bm_good_suffix[m - 1 - suffix[i]] = m - 1 - i # 开始 Boyer–Moore 匹配 i, j = 0, 0while j <= n - m: i = m - 1 while s1[i + j] == s2[i]: i -= 1 if i < 0: break if i < 0: # do something if match j += bm_good_suffix[0] else: j += max(bm_good_suffix[i], bm_bad_ch[s1
多模式匹配
多模匹配是用多个模式串来匹配一个输入串，但并不是简单的单模匹配的叠加，多个模式串直接可能存在某些匹配联系，可以利用他们之间的匹配关系进一步加速匹配。
AC自动机
AC自动机主要用于解决多模式串的匹配问题，是字典树(trie树)的变种，一种伪树形结构(主体是树形的，但是由于加入了失败指针，使得它变成了一个有向图)；trie图(我的理解^_^)是对AC自动机的一种改造，使得图中每个结点都有MAXC条出边(MAXC表示该图的字符集合大小), trie图上的每个结点代表一个状态，并且和AC自动机的结点是一一对应的。
AC自动机和KMP的基本思想一致，在不匹配时，模式串上的指针不会直接跳到最初，也是和KMP思想一样寻找上一个能匹配的状态。
AC自动机的预处理复杂度为O(m + k)，其中k为各模式串的总长度，搜索复杂度为O(n + m + z)，z 代表模式串在输入串中出现的次数。
AC自动机的算法主要分为三个步骤：构造一个 Trie 树、构造失败指针和进行匹配。
AC算法大体上分为三步：
构建Trie前缀搜索树，并标注结束节点
设置每个节点的失配跳转(fail指针)并收集每个节点的所有匹配模式串
对输入串进行一次遍历，对于每个字符（字节）都去敏感词树型结构中，从当前结点位置开始匹配。
如果匹配成功，则当前结点，下移到对应的结点。如果当前结点为“结束节点”，则表示匹配成功；
如果匹配失败，则当前结点，跳转到该结点的失败结点，继续匹配，直到匹配成功或当前结点为根结点；
算法核心思想：
学习AC自动机(AC-Automan？艾斯奥特曼？-_-|||)之前，首先需要有字典树和KMP的基础，这是每一篇关于AC自动机的文章都会论及的，所以我也就例行提一下。
例如，有四个01字符串(模式串)，"01"、"10"、"110"、"11"，字符集合为{'0', '1'}。那么构造trie图分三步，首先建立字典树，然后构造失败指针，最后通过失败指针补上原来不存在的边，那么现在就分三步来讨论如何构建一个完整的trie图。
字典树
字典树是一种树形结构，它将所有的模式串组织在一棵树的树边上，它的根结点是一个虚根，每条树边代表一个字母，从根结点到任意一个结点的路径上的边的有序集合代表某个模式串的某个前缀。
如图1，绿色点为虚根，蓝色点为内部结点，红色点为终止结点，即从根结点到终止结点的每条路径代表了一个模式串，由于"11"是"110"的前缀，所以在图中"11"这两条边是这两个字符串路径的共用部分，这样就节省了存储空间，由于trie树的根结点到每个结点的路径(边权)都代表了一个模式串的前缀，所以它又叫前缀树。
字典树实际上是一个DFA(确定性有限状态自动机)，通常用转移矩阵表示。行表示状态，列表示输入字符，(行, 列)位置表示转移状态。这种方式的查询效率很高，但由于稀疏的现象严重，空间利用效率很低。所以一般采用压缩的存储方式即链表来表示状态转移，每个结点存储至少两个域：数据域data、子结点指针域next[MAXC](其中MAXC表示字符集总数)。
构造字典树的前提一般是给定一系列的模式串，然后对每个模式串进行插入字典树的操作，初始情况下字典树只有一个虚根，如图2所示，进行四个模式串的插入后就完成了图1中的字典树的构造，每次插入在末尾结点打上标记(图中红色部分)，可以注意到，第四次操作实际上没有生成新的结点，只是打了一个结尾标记，由于它的这个性质，使得字典树的结点数目不会很多，大大压缩了存储结构。具体实现方式和编码会在下文中详细讲解。
失败指针
给定一个目标串，要求在由模式串构建的字典树中查找这个目标串中有多少个模式串，我们可以设定一个指针p，初始状态下它指向根结点，然后从前往后枚举目标串，对每一个目标串中的字符c，如果在p指向结点的出边集合中能够找到字符c对应的边，那么将p指向c对应边的子结点，循环往复，直到匹配失败，那么退回到p结点的fail指针指向的结点继续同样的匹配，当遇到一个终止结点时，计数器+1。
这里的fail指针类似KMP的next函数，每个trie结点都有一个fail指针，如图3，首先将根结点的fail指针指向NULL，根结点的直接子结点的fail指针指向根结点，这一步是很显然的，因为当一个字符都不能匹配的时候肯定是要跳到字符串首重新匹配了，每个结点的fail指针都是由它父结点的fail指针决定的，所以一次BFS就可以把所有结点的fail指针逐层求解出来了，具体实现方式和编码会在下文中详细讲解。
trie图
为了方便描述，我们先把所有trie树上的结点进行编号，编号顺序为结点的插入顺序，根结点编号为0。如图4的第一个图，我们发现如果现在是1号状态(状态即结点)，当接收一个'1'这个字符，那么它应该进入哪个状态呢？答案很显然，是2号状态，因为沿着字符'1'的出边到达的状态正好是2号状态；但是如果接受的是'0'字符，我们发现1号状态没有'0'字符代表的出边，所以我们需要补上这条'0'边，但是这条边指向哪个状态呢？答案是1号状态的fail指针指向的状态的'0'出边对应的状态。我们发现这个状态正好是它自己，所以向自己补一条边权为'0'的边(图中的橙色边，边指向的结点称为当前状态的后继状态)。同样是利用BFS的方式逐层求解所有结点的后继状态。我们发现所有结点遍历完后，每个结点都有且仅有两条出边，这样一个trie图就诞生了。
今后几乎所有关于状态机的问题都是围绕图4的那个图展开的。
新手初看算法的时候总是一头雾水，即使看懂了也要花很大力气才能把代码写出来(至少我是这样的)，所以没有什么比直接阐述代码更加直观的了。
参考文章：
AC自动机 http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html
浅谈字符串匹配 https://blog.brickgao.com/2015/08/08/string-searching-algorithm/
模式匹配算法 https://blog.csdn.net/happyjacob/article/details/80850975
常用字符串匹配算法简介 https://cloud.tencent.com/developer/article/1496701
转载本站文章《符串匹配算-几种常见的概念粗讲》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/PatternMatching/8275.html