字符串模式匹配算法

这里讨论两种常见的字符串模式匹配算法，不讨论字符串的预处理。

关于对字符串进行搜索，请参考 Boyer-Moore 字符串搜索算法 (Wikipedia CN)

另外建议大家阅读 [Sunday 算法]

BF 算法 (Brute Force)

返回子串 Ptn 在主串 Tag 的第 pos 个字符后(含第 pos 个位置)第一次出现的位置，若不存在，则返回 -1，这里的位置全部以从 0 开始计算为准，其中 T 非空，0 <= pos <= Tlen。

使用 i 标记当前在 Tag 中匹配的字符的位置，初始值为 pos。 使用 j 标记 Ptn 中正在等待比较的位置，初始值为 0,下同。

int index(const string &Tag,const string &Ptn,int pos);

即对 Tag 的每一个字符与 Ptn 的字符进行逐字比较：

  • 若完整匹配则返回匹配成功的 pos 值。
  • 匹配过程中，对当前的 pos 值对应位置之后的每一字符进行 Ptn 的匹配，出现不符合的情况，则将 i 置为 pos + 1，j 置为 0；从当前 pos 值对应的下一个字符开始从头对 Ptn 进行匹配。
  • 若扫描完整个 Tag 都无法匹配，返回 -1.

该算法在最坏情况下的时间复杂度为 O(len(P)*len(T))，另外该算法的空间复杂度为 O(1)。

KMP 算法 (Kruth-Morris-Pratt)

上述算法的时间复杂度为乘积关系，是由于索引指针回溯引起的，针对上述不足，有了 KMP 算法。 KMP 算法的时间复杂度为 O(len(P)+len(T))，空间复杂度为 O(len(P))。这个算法改进的地方在于，不需要过度回溯索引指针 i，而是利用部分匹配结果尽可能的向远滑动，继续进行回溯。但是由于 Next 表的建立相对复杂，记忆性价比不高，在实际应用中也较少。更多使用 R-K 算法。

算法示例

Step 0: 比较开始。

     00000000001111111111222
i:   01234567890123456789012
Tag: ABC ABCDAB ABCDABCDABDE
Ptn: ABCDABD
j:   0123456

Step 1: 从头比较，比较到 Tag[3] = ‘ ‘ 时发现与 Ptn[3] = ‘D’ 不符。我们已知 Tag[1~3] 与 Ptn[0] 不符，接下来略过这些字符，令 i = 4, j = 0

     00000000001111111111222
i:   01234567890123456789012
Tag: ABC ABCDAB ABCDABCDABDE
Ptn:     ABCDABD
j:       0123456

Step 2：这时我们继续检索 Tag，发现仍不匹配，但是 Tag[8~9] 对应的 ‘AB’ 出现了两次，故可以作为下次比较的起始点，我们令 i = 8, j = 2，继续比较。

     00000000001111111111222
i:   01234567890123456789012
Tag: ABC ABCDAB ABCDABCDABDE
Ptn:         ABCDABD
j:           0123456

Step 3：到 i = 10 时，此时我们放弃比较重复内容，比较 i = 10 与 j = 2 发现出现不符。接下来，由于 ‘AB’ 重复出现，我们从 i = 11, j = 0 开始比较。

     00000000001111111111222
i:   01234567890123456789012
Tag: ABC ABCDAB ABCDABCDABDE
Ptn:            ABCDABD
j:              0123456

Step 4：到 i = 17, j = 6 出现不相同异常，我们采取一贯的做法，令 i = 15, j = 2 继续搜索。

     00000000001111111111222
i:   01234567890123456789012
Tag: ABC ABCDAB ABCDABCDABDE
Ptn:                ABCDABD
j:                  0123456

Step 5：此时我们找到完全匹配的字符串，初始位置为 15, 返回 i。比较结束。

失配函数

特殊情况：当一个失配出现在模式串的此次匹配最开始，此时无法回退，我们置 j = -1，跳到模式串的开头字符。

关键：建立 next 表。

理清匹配过程

假设现在文本串 Tag 匹配到 i 位置，模式串 Ptn 匹配到 j 位置：

  • 如果 j == -1 或当前字符匹配成功（即 Tag[i] == Ptn[j]），都令 i++，j++，继续匹配下一个字符；
  • 如果当前字符匹配失败（即 Tag[i] != Ptn[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串 Ptn 相对于文本串 Tag 向右移动了 (j – next [j]) 位。
    换言之，当匹配失败时，模式串向右移动的位数为： 失配字符所在位置 – 失配字符对应的 next 值（next 数组的求解会在下文中详细阐述），即移动的实际位数为：(j – next[j]) ，且此值大于等于 1。

很快，你也会意识到 next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果 next [j] = k，代表 j 之前的字符串中有最大长度为 k 的相同前缀后缀。

  • 这也意味着在某个字符失配时，该字符对应的 next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到 next [j] 的位置）。如果 next [j] 等于 0，则跳到模式串的开头字符，若 next [j] = k 且 k > 0，代表下次匹配跳到 j 之前的某个字符，而不是跳到开头，且具体跳过了 k 个字符。

这里，我们明确一点，next 表的产生实际只与 模式串及其子串 有关。

关于 Next 表的建立

  1. 寻找前缀后缀的公共元素最大长度

对于 Ptn = p0 p1 … pj ，寻找 Ptn 中长度最大且相等的前缀和后缀。若存在 p0 p1 … pk = p(j-k) p(j-k+1)… pj，那么在包含 pj 的模式串中有最大长度为 k+1 的相同前缀和后缀。

  1. 求 next 数组

next 数组考虑的是除当前字符外的最长相同前缀后缀，所以通过第 ① 步骤求得各个前缀后缀的公共元素的最大长度后，只要稍作变形即可：将第 ① 步骤中求得的值整体右移一位，然后初值赋为 -1 。

  1. 根据 next 数组进行匹配

匹配失配，j = next[j] ，模式串向右移动 j – next[j] 位。即当 模式串的后缀 p(j-k) p(j-k+1) … p(j-1) 和 源串 s(i-k) s(i-k+1) … s(i-1) 匹配成功，但最后一位 pj 和 si 匹配失败的时候，因为 next[j] = k，等价于 在不包含 pj 的模式串中有最大公共长度为 k 的前缀后缀，即 p0 p1 … p(k-1) = p(j-k+) p(j-k+1) … p(j-1) ，接下来我们令 j = next[j] ，从而让字符串右移 next[j] 位，此时模式串的最大长度公共前缀 p0 p1 … p(k-1) 对应这 s(i-k) s(i-k+1) … s(i-1), 实现了跳过公共前后缀的匹配，直接匹配 pk 和 si 继续匹配。

学习之后实验

原字符串 TAG： BBC ABCDAB ABCDABCDABDE
匹配模式串 PTN:               ABCDABD
  1. 寻找最长前缀后缀
子串前缀后缀最大公共元素长度
A//0
ABAB0
ABCA,ABC,BC0
ABCDA,AB,ABCD,CD,BCD0
ABCDAA,AB,ABC,ABCDA,DA,CDA,BCDA1
ABCDABA,AB,ABCD,ABCDAB,AB,DAB,CDAB,BCDAB2
ABCDABDA,AB,ABC,ABCD,ABCDA,ABCDABD,BD,ABD,DABD,CDABD,BCDABD0

对应生成的公共元素最大长度表如下：

字符ABCDABD
最大前缀后缀公共元素长度0000120
  1. 基于最大长度表生成 NEXT 表

原来 next 数组的求解竟然如此简单：就是找最大对称长度的前缀后缀，然后整体右移一位，初值赋为-1（当然，你也可以直接计算某个字符对应的next值，就是 看这个字符之前的字符串中有多大长度的相同前缀后缀）

模式串子串ABCDABD
NEXT-1000012

备注：这里其实 next[A0] == -1，意在告诉程序当一开始模式串第一个字符与文本串就不匹配时，可以放弃此次匹配，直接将模式串不断右移一位开始下一次匹配。

  1. 初始匹配
原字符串 TAG： BBC ABCDAB ABCDABCDABDE
匹配模式串 PTN:    ABCDABD

这里，我们从一开始就发现没有匹配的字符，于是不断后移一位。移动到 i = 4 时，与第五个字符 A 匹配成功，接下来，一直向下匹配，匹配到 j = 6 （字母 D2）时，发生失配。这时将模式串后移，后移 j = j – next[D2] = 6 – 2 = 4 位。

  1. 第二次匹配
原字符串 TAG： BBC ABCDAB ABCDABCDABDE
匹配模式串 PTN:        ABCDABD

这里，移动到 i = 8 时，与第九个字符 A 匹配成功，接下来，一直向下匹配，匹配到 j = 2 （字母 C）时，发生失配。这时将模式串后移，后移 j = j – next[C] = 2 – 0 = 2 位。

  1. 第三次匹配， (TAG[10] = ‘ ‘) != (PTN[0] == ‘A’)，后移 j = j – next[A1] = 0 – (-1) = 1 位。
原字符串 TAG： BBC ABCDAB ABCDABCDABDE
匹配模式串 PTN:          ABCDABD
  1. 第四次匹配， (TAG[17] = ‘C’) != (PTN[6] == ‘D’)，后移 j = j – next[D2] = 6 – 2 = 4 位。
原字符串 TAG： BBC ABCDAB ABCDABCDABDE
匹配模式串 PTN:           ABCDABD
  1. 第五次匹配， 匹配成功。
原字符串 TAG： BBC ABCDAB ABCDABCDABDE
匹配模式串 PTN:               ABCDABD

关于逍爷的讲解

试比较：

失配时，模式串向右移动的位数为：失配字符所在位置 – 失配字符对应的 next 值

失配时，模式串向右移动的位数为：已匹配字符数 – 失配字符的上一位字符所对应的最大长度值

其实二者等价，只不过讲法不同罢了。

根据《最大长度表》，失配时，模式串向右移动的位数 = 已经匹配的字符数 – 失配字符的上一位字符的最大长度值。

而根据《next 数组》，失配时，模式串向右移动的位数 = 失配字符的位置 – 失配字符对应的 next 值。

其中，从 0 开始计数时，失配字符的位置 = 已经匹配的字符数（失配字符不计数），而失配字符对应的next 值 = 失配字符的上一位字符的最大长度值，两相比较，结果必然完全一致。

相关代码

BF

int ViolentMatch(char* s, char* p)
{
    int sLen = strlen(s);
    int pLen = strlen(p);

    int i = 0;
    int j = 0;
    while (i < sLen && j < pLen)
    {
        if (s[i] == p[j])
        {
            //①如果当前字符匹配成功（即 Tag[i] == Ptn[j]），则 i++，j++    
            i++;
            j++;
        }
        else
        {
            //②如果失配（即 Tag[i]! = Ptn[j]），令i = i - (j - 1)，j = 0    
            i = i - j + 1;
            j = 0;
        }
    }
    //匹配成功，返回模式串 Ptn 在文本串 Tag 中的位置，否则返回 -1
    if (j == pLen)
        return i - j;
    else
        return -1;
}

KMP

int KmpSearch(char* s, char* p)
{
    int i = 0;
    int j = 0;
    int sLen = strlen(s);
    int pLen = strlen(p);
    while (i < sLen && j < pLen)
    {
        //①如果当前字符匹配成功（即 Tag[i] == Ptn[j]），都令 i++，j++    
        if (s[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            //②如果当前字符匹配失败（即 Tag[i] != Ptn[j]），则令 i 不变，j = next[j]    
            //next[j]即为j所对应的next值      
            j = next[j];
        }
    }
    if (j == pLen)
        return i - j;
    else
        return -1;
}

改进后的 Next 数组的递归生成

void GetNextval(char* p, int next[])
{
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
        //p[k]表示前缀，p[j]表示后缀  
        if (k == -1 || p[j] == p[k])
        {
            ++j;
            ++k;
            //较之前next数组求法，改动在下面4行
            if (p[j] != p[k])
                next[j] = k;   //之前只有这一行
            else
                //因为不能出现p[j] = p[(next[j])]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
                next[j] = next[k];
        }
        else
        {
            k = next[k];
        }
    }
}

拓展延伸： Sunday 算法

Boyer-Moore 算法

略显复杂，略去不提，看文章开头有 Wikipedia 链接，也是一个改进算法。

该算法从模式串的尾部开始匹配，且拥有在最坏情况下O(N)的时间复杂度。在实践中，比KMP算法的实际效能高。

BM算法定义了两个规则：

坏字符规则：当文本串中的某个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 – 坏字符在模式串中最右出现的位置。此外，如果”坏字符”不包含在模式串之中，则最右出现位置为-1。

好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 – 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。

Sunday 算法

上文中，我们已经介绍了 KMP 算法和 BM 算法，这两个算法在最坏情况下均具有线性的查找时间。但实际上， KMP 算法并不比最简单的 C 库函数 strstr() 快多少，而 BM 算法虽然通常比 KMP 算法快，但 BM 算法也还不是现有字符串查找算法中最快的算法，本文最后再介绍一种比 BM 算法更快的查找算法即 Sunday 算法。

Sunday 算法由 Daniel M.Sunday 在 1990 年提出，它的思想跟 BM 算法很相似：

只不过 Sunday 算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1；否则，其移动位数 = 模式串中最右端的该字符到末尾的距离 + 1。其时间复杂度最好情况为 O(m/n) ，最差情况为 O(m*n)。

下面举个例子说明下 Sunday 算法。假定现在要在文本串 “substring searching algorithm” 中查找模式串 “search” 。

刚开始时，把模式串与文本串左边对齐：

substring searching algorithm
search
^

结果发现在第 2 个字符处发现不匹配，不匹配时关注文本串中参加匹配的最末位字符的下一位字符，即标粗的字符 i，因为模式串 search 中并不存在 i，所以模式串直接跳过一大片，向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7，从 i 之后的那个字符（即字符 n ）开始下一步的匹配，如下图：

substring searching algorithm　　　
       search
　　　　^

结果第一个字符就不匹配，再看文本串中参加匹配的最末位字符的下一位字符，是 ‘r’ ，它出现在模式串中的倒数第 3 位，于是把模式串向右移动 3 位（ r 到模式串末尾的距离 + 1 = 2 + 1 = 3 ），使两个 ‘r’ 对齐，如下：

substring searching algorithm
　　　　   search
　　　　　　　 ^

匹配成功。

回顾整个过程，我们只移动了两次模式串就找到了匹配位置，缘于 Sunday 算法每一步的移动量都比较大，效率很高。完。

一点点碎碎念

学院现在的课程设置问题非常严重，图灵机、有限状态自动机、算法优化、通信原理、量子物理各方面的课程缺乏严重，导致学生学习专业课程时出现了极大的知识断层，课外各种杂事颇多，时间非常紧张，需要学生花大量课后时间充电。

本来计算机相关行业，知识更新速度快，入门门槛高、相对复杂，基础知识要求广泛，现在却这样，大学真的很忙。每天都是高压锅生活。为了光明的未来和亲爱的钰，还是更加努力吧！

关于昨天的汇编文章：其实用什么平台并不重要，作为入门者，你需要明白的只是老师为什么让你这样做，这样做背后的计算机原理是什么。在具体实践上，如何把本来 Windows 上的东西尽量在 Linux 上完美复现或者找到替代品。这样就好了。我知道 Windows 开发的公司仍然是绝大多数，但是在 Linux 平台写代码给了很多人一种专注于代码实现本身的感觉（虽然初始状态的学习曲线非常抖），不用像 Windows 一样各种折腾环境。更何况，Arch Linux 的系统设计注重代码正确、优雅和极简主义，期待用户能够愿意去理解系统的操作，这样的系统正是我们有一点点基础的初学者所需要的。日常用 Linux 多学点底层的东西同时又提高效率又何妨？

Reference

  • https://blog.csdn.net/ns_code/article/details/19286279
  • https://zh.m.wikipedia.org/zh-cn/%E5%85%8B%E5%8A%AA%E6%96%AF-%E8%8E%AB%E9%87%8C%E6%96%AF-%E6%99%AE%E6%8B%89%E7%89%B9%E7%AE%97%E6%B3%95
  • http://saturnman.blog.163.com/blog/static/5576112010969957130/
  • https://blog.csdn.net/v_july_v/article/details/7041827 Strongly Recommended
Last modified: 2020-01-22

Author