模式匹配算法

1. 模式匹配

模式匹配是数据结构中字符串的一种基本运算，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串，这就是模式匹配。

假设P是给定的子串，T是待查找的字符串，要求从T中找出与P相同的所有子串，这个问题成为模式匹配问题。P称为模式，T称为目标。如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功；否则匹配失败。

2. 常见模式匹配算法

2.1 朴素的模式匹配算法

假设我们要从主串s="goodgoogle"找到t="google"这个子串的位置，我们需要下列步骤：

（1）主串s的第1位开始，s与t前三个字符都匹配成功，第四个字符不匹配（竖线表示相等，闪电状弯折表示不想等）.

（2）主串s的第2位开始，匹配失败

（3）主串s的第3位开始，匹配失败

（4）主串s的第4位开始，匹配失败

（5）主串s的第5位开始，s与t，6个字符全部匹配成功

对主串s的每一个字符作子串t开头，要与匹配的字符串t进行匹配。对主串s作大循环，每一个字符开头作t长度的小循环，直到匹配成功或者全部遍历完为止。

图1

时间复杂度：

最好情况：如"googlegood"中找"google"，第一个开始位置就匹配，时间复杂度为O(1).

其次：比如"abcdefgoogle"中找"google"，时间复杂度O(n+m)，其中n为主串长度，m为子串长度，根据等概率原则，平均（n+m）次查找，时间复杂度为O(n+m)

最坏的情况，每次不成功都发生在串t的最后一个字符，比如子串t="0000000001"，9个"0"和一个"1"，主串s="00000000000000000000000000000000000000000000000001"，49个"0"和一个"1"时间复杂度为O((n-m+1)*m)

2.2 KMP匹配算法

（1）假设主串s="abcdefgab"，t="abcdex"。"abcdex"的首字符"a"与后面的串"bcdex"中任何一个字符都不相等，子串t与主串s的前5个字符分别相等，意味着子串t的首字符"a"不可能与s串的第2位到第5位的字符相等。

图2

（2）假设s="abcababca"，t="abcabx"。子串t中有重复字符。第一步，前5个字符相等，第6个字符不相等，根据前面的经验，t的首字符"a"与t中第二位、第三位字符均不等，不需要判断。子串t中第1位与第4位相等，第2位与第5位相等；主串s中第4位，第5位分别与子串t中第4位，第5位相等，意味着子串的第1位与第2位分别与主串第4位与第5位相等，不需要判断。

图3

总结：i值不回溯，j值的变化只与子串有关，取决于t串中的结构中是否有重复的字符串。我们把t串各个位置的变化定义为一个数组next，next的长度就是t串的长度。

图4 图5

时间复杂度：对于get_next来说，t的长度为m，由于只涉及到简单循环，其时间复杂度为O(m)；i的值不回溯，主串的长度为n，while循环的时间复杂度为O(n)，因此整个代码的数减复杂度为O(n+m)

(3)KMP模式匹配算法改进

KMP匹配算法还是有缺陷的，比如子串s="aaaabcde"，子串t="aaaaax"，子串t的next为012345.

图6

我们发现②③④⑤步骤是多余的。由于子串t中第2、3、4、5个位置上的字符串和守卫上的字符串相等，那么可以用首位next[1]来代替后续与它相等的字符后续的next[j]，由于子串t中第2、3、4、5个位置上的字符串和首位上的字符串相等，那么可以用首位next[1]来代替后续与它相等的字符后续的next[j]。

2.3 BM匹配算法

Boyer-Moore（BM）算法是一种基于后缀匹配的模式串匹配算法，后缀匹配就是模式串从右到左开始比较，但模式串的移动还是从左到右的。字符串匹配的关键就是模式串的如何移动才是最高效的，Boyer-Moore为了做到这点定义了两个规则：坏字符规则和好后缀规则，下面图解给出定义：

图7

2.3.1 坏字符规则

（1）如果坏字符没有出现在模式字符中，则直接将模式串移动到坏字符的下一个字符：

图8（坏字符c，没有出现模式串P中，直接将P移动c的下一个位置）

（2）如果坏字符出现在模式串中，则将模式串最靠近好后缀的坏字符（当然这个实现就有点繁琐）与母串的坏字符对齐：

图9（如果模式串P是babababab，则是将第二个b与母串的b对齐）

2.3.2 好后缀规则

好后缀规则分三种情况：

（1）模式串中有子串匹配上好后缀，此时移动模式串，让该子串和好后缀对齐即可，如果超过一个子串匹配上好后缀，则选择最靠靠近好后缀的子串对齐。

图10

（2）模式串中没有子串匹配上后后缀，此时需要寻找模式串的一个最长前缀，并让该前缀等于好后缀的后缀，寻找到该前缀后，让该前缀和好后缀对齐即可.

图11

其实，1和2都可以看成模式串还含有好后缀串（好后缀子串也是好后缀）.

（3）模式串中没有子串匹配上后后缀，并且在模式串中找不到最长前缀，让该前缀等于好后缀的后缀。此时，直接移动模式到好后缀的下一个字符。

图12

2.4 AC多模式算法

Aho-Corasick算法又叫AC自动机算法，是一种多模式匹配算法。Aho-Corasick算法可以在目标串查找多个模式串，出现次数以及出现的位置。

2.4.1 Aho-Corasick算法原理

Aho-Corasick算法主要是应用有限自动机的状态转移来模拟字符的比较，下面对有限状态机做几点说明：

图13

上图是由多模式串{he,she,his,hers}构成的一个有限状态机：

1.该状态当字符匹配是按实线标注的状态进行转换，当所有实线路径都不满足（即下一个字符都不匹配时）按虚线状态进行转换。

2.对ushers匹配过程如下图所示：

图14

当转移到红色结点时表示已经匹配并且获得模式串

2.4.2 Aho-Corasick算法步骤

Aho-Corasick算法和前面的算法一样都要对模式串进行预处理，预处理主要包括字典树Tire的构造，构建状态转移表（goto），失效函数（failure function），输出表（Output）。

Aho-Corasick算法包括以下3个步骤

                1.构建字典树Tire

                2.构建状态转移表，失效函数（failure function），输出表（Output）

                3.搜索路径（进行匹配）

下面3个步骤分别进行介绍

构建字典树Tire

        Tire是哈希树的变种，Tire树的边是模式串的字符，结点就是Tire的状态表，下图是多模式串{he,she,his,hers}的Tire树结构：

图15

构建goto函数、failure function和Output函数     

         goto函数（状态转移函数）：goto(pre,v)=next,完成这样的任务：在当前状态pre，输入字符v，得到下一个状态next，如果没有下个状态则next=failure。 

图16

     failure function：失效函数是处理当前状态是failure时的处理。 

图17

    output函数：当完成匹配是根据状态输出匹配的模式串。

图18

多模式串{he,she,his,hers}最终的有限状态机图:

3. 模式匹配算法的本质

扫描+特征比较

扫描：

        1、逐位扫描；

        2、边界特征扫描；

特征提取：核心是目标特征分析

        1、整体特征：整体hash；

        2、边界特征：忽略中间量，仅对首尾做特征提取；

        3、分析特征：适合有重复字符的匹配模式；

        4、统配特征：边界特征+限制特征+位数；