【算法】----BF算法&KMP算法

请想象一个情景：

当你脑海中突然浮现出一个词，你该怎么去找到这个词的有关内容？

打开我们浏览器的搜索框，输入你想的这个词，然后点击Enter。浏览器就会自动搜索与该词匹配的内容。

这个过程实际上可以简化成以下形式：

有一个文本串S，一个模式串P（也叫子串），现在要查找P在S中的位置。

我们今天所讨论的两个算法就是有关该过程的算法。

事实上，对于检索，无非就是两个字符串的匹配过程，模式串是你想要匹配的串，主串是你搜索所在串。

针对模式串中的一个个字符与主串进行匹配，

匹配成功则继续往后匹配；

匹配失败则跳过该串段继续匹配，直到主串中出现与模式串完全相同的串段，此时则成功找到。

所以检索无非就是模式匹配的过程。

BF算法和KMP算法是较为著名的模式匹配算法，接下来作出详细介绍。

BF算法

BF算法(Brute-Force)也称为暴力算法，其核心原理是逐个比较文本串和模式串的字符，如果匹配失败，则通过向右移动模式串的位置，再次进行比较。

算法步骤

我们设主串和模式串中的字符位置分别为i和j

• 如果当前字符匹配成功（即T[i] == P[j]），则i++，j++，继续匹配下一个字符；
• 如果当前字符匹配失配（即T[i]! = P[j]），则令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

举例：

假设我们有一个文本串T为：“ABCDABCDABCE”，以及一个模式串P为：“ABCE”，我们要在文本串T中查找是否存在模式串P。

首先，我们将文本串T和模式串P在一条直线上对齐：

文本串T:  ABCDABCDABCE
模式串P:  ABCE

然后，我们从文本串T的第一个字符开始和模式串P的第一个字符比较：

第一次比较：'A’和’A’相等。

文本串T:  ABCDABCDABCE
模式串P:  A

第二次比较：'B’和’B’相等。

文本串T:  ABCDABCDABCE
模式串P:  AB

第三次比较：'C’和’C’相等。

文本串T:  ABCDABCDABCE
模式串P:  ABC

第四次比较：'D’和’E’不相等，出现失配。

文本串T:  ABCDABCDABCE
模式串P:  ABCE

在匹配失败后，我们将模式串P向右移动一位，重新从文本串T的当前位置和模式串P的第一个字符开始比较：

文本串T:  ABCDABCDABCE
模式串P:   A

第一次比较：'A’和’B’不相等。出现失配。

那么再将模式串P向右移动一位，重新从文本串T的当前位置和模式串P的第一个字符开始比较：

文本串T:  ABCDABCDABCE
模式串P:    A

第一次比较：'A’和’C’不相等。出现失配。

继续类似的比较过程，直到文本串T遍历完毕。

代码演示

根据上述过程我们可以写出BF算法的代码：

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

我们发现这种确实可以被称作暴力解法：无论后面的元素是否匹配，模式串P都会回溯到它的第一个字符开始重新比较，而例如在第二次重新匹配的过程中，实际上是必定失配的，从而又要继续回溯再重新比较，属实暴力且死板。

时间复杂度

BF算法的时间复杂度取决于文本串T的长度为n，模式串P的长度为m。在最坏情况下，BF算法需要在文本串T的每个位置上都尝试匹配模式串P，因此时间复杂度为O(n*m)。

在实际情况下，BF算法的效率并不高，特别是当文本串T和模式串P的长度很大时。对于较长的文本串和模式串，BF算法的时间复杂度可能会导致性能问题。

那么有没有另外一种解法，可以避免不必要的i回溯，而只移动j即可呢？这样所需要消耗的时间就会大大减少。

答案就是KMP算法。

KMP算法

KMP算法的核心思想是利用模式串自身的特点来加速匹配过程，避免重复匹配。

算法步骤

我们设主串和模式串中的字符位置分别为i和j

• 如果当前字符匹配成功（即T[i] == P[j]），步骤与暴力匹配法相同，则i++，j++，继续匹配下一个字符；
• 如果当前字符匹配失配（即T[i]! = P[j]），则根据最大长度表计算需要移动的位数。

这里由于匹配成功的情况与前面BF相同，所以我们只对匹配失败进行讨论。

公式

需要移动的位数=已匹配的字符数-失配字符的上一位字符对应的最大长度；

这里我们理解一下具体的步骤，以及为什么是上述的公式。

为什么是算出最大长度的相同前缀和后缀

因为当最大长度的前缀和后缀相同的时候，移动已匹配的字符数-最大长度即可保证不会多移动或者少移动。如图：

蓝色部分的字符个数即是我们需要移动的字符个数，而黄色部分的字符个数即是最大相同长度，而黄色+蓝色部分即是

已匹配的字符个数。

所以有：已匹配的字符个数=最大相同长度+需要移动的字符个数，从而得出：

需要移动的字符个数=已匹配的字符个数-最大相同长度。

注意：我们要找的是相同前后缀的最长长度，注意一定是要最长的。并且不能是字符串本身。（如果是本身便没有意义了）

最大长度表是什么

上述过程我们所提到的最大长度表指的是模式串中最大长度的相同前缀和后缀，在公式中的最大相同长度就是对照该表得出的。

如何求最大长度表呢？在具体的代码中，我们需要使用一个函数来求出最大长度表，并且在具体的算法实现中，让其对应求出所需要移动的字符个数。这个时候我们就需要用到next数组。

next数组

首先我们最需要知道的是：next数组的作用就是求出最大长度表。

最大长度表并不是使用next数组求出来的对照表，而是指的是next数组本身。next数组存储的是最大长度表，用于帮助算法快速定位匹配位置；

而由于数组的初始下标为0的限制，在书写上两者会有以下的差异：

next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1。（因为数组的初始下标为0）

也就是 j-next[j]

问题的关键就是寻找模式串中最大长度的相同前缀和后缀，找到了模式串中每个字符之前的前缀和后缀公共部分的最大长度后，便可基于此匹配。而这个最大长度便正是next 数组要表达的含义。

next的具体求法

针对主串和模式串来进行字符匹配，而p[k]是主串正在被匹配的子字符串的元素，p[j]是正在进行匹配的模式串的元素。

• 如果模式串的第i个字符和第j个字符相等(即p[k ] == p[j]），则next[j + 1] = next[j] + 1 = k + 1，同时i和j都向后移动一位。

也就是说此时：t(1)t(2)…t(k)=t(j-k+1)t(j-k+2)…t(j)

那么next[j + 1] = next[j] + 1 = k + 1。代表此字符前的模式串中，有长度k+1 的相同前缀后缀。

• 如果模式串的第i个字符和第j个字符不相等（即p[k ] ≠ p[j]），则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。 也就是说此时正在匹配的字符失配，而算出的next[ j + 1 ] = next[k] + 1就是最大长度。

注意：主串是永远不动的，动的一直都是子串也就是模式串，也就是说i永不递减，只有j会递减。

next数组的代码使用递推求解，好处在于会不断利用已掌握的信息来避免重复的运算。

针对上述的字符不相同的情况，我们对此进行更详细的解答。

首先我们应该以一种类动态规划的思想去思考这个问题：动态规划中，我们会利用已知的子问题来解决更大规模的问题，避免重复的计算；而在KMP中，next数组存储了模式串中的最大长度，这个最大长度会帮助我们跳过一些不必要的比较，这个在后面会提到。

接下来，我们进行模拟。

当匹配不成功时：

查找是否存在更短的共同前后缀，如果找到了，则重新从此处再做一次KMP算法。

例如，有以下字符串：

A  B  A  C  A  B  A  B
0  1  2  3  4  5  6  7

扫描到 6 号位的 A 时，最长公共前后缀是 ABA；而扫描到 7 号位的 B 时，ABAC 和 ABAB 不匹配了，即原来的最长公共前后缀失配。

这时候我们要做的事情就是，找上一次匹配中次长的公共前后缀，看与 7 号位的 B 拼接起来是否能匹配。因为我们的目的就是为了继续匹配，但是由于最长的已经用过了，所以就找次长的。

这时候，注意到上一次扫描中 0 ~ 2 位的 ABA 是和 4 ~ 6 位的 ABA 完全相同的，所以考察上一次匹配中次长的公共前后缀，只能在考察上一次匹配中的最长公共前后缀中寻找，也就是说，只能考察 ABA 中更短的 BA、A 是否是次长的，而这直接在前面一个 ABA 中考察就行（因为前后两个ABA是一样的）。（我们的目的就是要找最长公共前后缀）

所以我们把 ABA C ABA 的中间部分（C）和后缀（ABA）直接抛弃，等效于一个串 ABA（也就是前缀）与 B 拼接成 ABAB。这样再来计算第 7 位的 B 的 next 值，等价于计算 ABAB 第 3 位的 B 的 next 值。

代码演示

void GetNext(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]) 
    {
      ++k;
      ++j;
      next[j] = k;
    }
    else 
    {
      k = next[k];
    }
  }
}

这样我们就能计算出我们需要的next值，从而得到最大长度表，然后再将该表代入到需要移动字符数的计算公式中，继续匹配下去。

当然

接下来根据KMP算法的主要核心以及next数组举例介绍流程：

假设我们有文本串 T = "ABCABABCABD" 和模式串 P = "ABCABD"。我们需要在文本串 T 中找到模式串 P 的出现位置。

步骤1: 构建next数组

首先，我们需要为模式串 P 构建一个next数组。这个数组用于在不匹配的情况下，告诉我们应该从模式串的哪个位置重新开始匹配。

对于模式串 P = "ABCABD"，我们如下构建next数组：

1. 初始化：next[0] = -1 (当模式串的第一个字符不匹配时，我们没有更早的位置可以回退到)
2. 从P[1]开始，比较前后缀：

• j = 0，next[1] = 0 （没有相同的前后缀）
• j = 1，比较 P[0] 和 P[1]，不相同，next[2] = 0
• j = 2，比较 P[0] 和 P[2]，不相同，next[3] = 0
• j = 3，比较 P[1] 和 P[3]，相同，next[4] = 1
• j = 4，比较 P[2] 和 P[4]，相同，next[5] = 2
• j = 5，比较 P[3] 和 P[5]，不相同，next[6] = 0

最终的next数组为 [-1, 0, 0, 0, 1, 2, 0].

步骤2: 使用next数组进行匹配

现在我们使用next数组来匹配文本串 T 和模式串 P：

T = ABCABABCABD
P = ABCABD

1. 初始位置：i = 0,j = 0

• T[0] = P[0] (A = A)，匹配，i = 1, j = 1
• T[1] = P[1] (B = B)，匹配，i = 2, j = 2
• T[2] = P[2] (C = C)，匹配，i = 3, j = 3
• T[3] = P[3] (A = A)，匹配，i = 4, j = 4
• T[4] = P[4] (B = B)，匹配，i = 5, j = 5
• T[5] = P[5] (C ≠ D)，不匹配，根据 next[5] = 2，j = 2

2. 继续匹配：

• T[5] = P[2] (C = C)，匹配，i = 6, j = 3
• T[6] = P[3] (A = A)，匹配，i = 7, j = 4
• T[7] = P[4] (B = B)，匹配，i = 8, j = 5
• T[8] = P[5] (D = D)，匹配，i = 9, j = 6（模式串匹配完成）

匹配成功，模式串 P 在文本串 T 中的起始位置为 3 (从0开始计数)。

通过这个例子，我们可以看到KMP算法如何有效地使用next数组来避免不必要的比较，从而加快字符串匹配的过程。

nextval（next的扩展优化）

请看以下举例

T = AAABAAAAB
P = AAAAB

当i=4，j=4时，我们发现此时的字符不匹配，那么根据next[j]的指示我们还需进行：i=4不变，分别j=3、j=2、j=1的三次比较。

但是实际上模式串中的1_{3以及第4个字符全都相等，因此将1}3这3个字符再去和主串的第4个字符比较实际上是和j=4时的情况是一样的，是会失配的。

那么我们应该如何避免并跳过这种重复的比较，直接进行i=5、j=1的比较呢？

这里则可以对next进行优化得到nextval。

//优化过后的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];
    }
  }
}

这个代码就完美地规避了上述讲到的问题。nextval可以实现跳跃到一个更远的位置进行匹配，从而减少不必要的比较次数。

接下来的代码是整个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)
  {
    //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++    
    if (j == -1 || s[i] == p[j])
    {
      i++;
      j++;
    }
    else
    {
      //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]    
      //next[j]即为j所对应的next值      
      j = next[j];
    }
  }
  if (j == pLen)
    return i - j;
  else
    return -1;
}

时间复杂度

KMP算法的时间复杂度分析如下：

1. 构建next数组的时间复杂度：构建next数组的时间复杂度是O(m)，其中m是模式串的长度。
   
2. 匹配过程的时间复杂度：在KMP算法中，匹配过程的时间复杂度主要取决于文本串的长度n。在匹配过程中，每次失配时，根据next数组回退到一个更早的位置重新开始匹配，而不会重复比较已经匹配过的字符。因此，匹配过程的时间复杂度是O(n)。
   

综合以上两点，KMP算法的总体时间复杂度为O(m + n)，其中m是模式串的长度，n是文本串的长度。相比于朴素的字符串匹配算法的**O(m*n)**时间复杂度，KMP算法通过利用next数组的特性，在匹配过程中避免了不必要的比较，从而实现了更高效的字符串匹配。

KMP的使用场景

总的来说，KMP算法适用于需要快速匹配模式串的场景，特别是在文本串较长、模式串较短的情况下。为什么呢？我们参照KMP的时间复杂度，O(m + n)，m是模式串的长度，n是文本串的长度：

• 长文本串（针对n）：KMP算法适用于处理长文本串，因为它能够在匹配过程中避免不必要的比较，从而减少比较次数，提高匹配效率。
• 短模式串（针对m）：KMP算法在处理短模式串时效果显著，因为其时间复杂度不会随着模式串长度的增加而大幅增加。
• 需要多次匹配：如果需要在同一文本串中多次匹配同一个模式串，KMP算法可以提高效率，因为构建好的next数组可以被重复利用。

常用用途：

• 字符串搜索：KMP算法常用于在文本串中搜索特定的模式串，例如搜索关键字、词语等。
  
• 文本处理：在文本处理领域，KMP算法可以用于文本匹配、替换等操作。
  
• 编译器设计：在编译器的词法分析阶段，KMP算法用于匹配词法单元，如关键字、标识符等。
  
• 网络协议：在网络协议中，KMP算法可以用于匹配特定的模式，例如在URL匹配、数据包匹配等场景中。
  *是文本串的长度：
  
• 长文本串（针对n）：KMP算法适用于处理长文本串，因为它能够在匹配过程中避免不必要的比较，从而减少比较次数，提高匹配效率。
  
• 短模式串（针对m）：KMP算法在处理短模式串时效果显著，因为其时间复杂度不会随着模式串长度的增加而大幅增加。
  
• 需要多次匹配：如果需要在同一文本串中多次匹配同一个模式串，KMP算法可以提高效率，因为构建好的next数组可以被重复利用。
  

常用用途：

• 字符串搜索：KMP算法常用于在文本串中搜索特定的模式串，例如搜索关键字、词语等。
• 文本处理：在文本处理领域，KMP算法可以用于文本匹配、替换等操作。
• 编译器设计：在编译器的词法分析阶段，KMP算法用于匹配词法单元，如关键字、标识符等。
• 网络协议：在网络协议中，KMP算法可以用于匹配特定的模式，例如在URL匹配、数据包匹配等场景中。