数据结构与算法（九）——字符串的匹配算法

题目：

有一个主串S = {a, b, c, a, c, a, b, d, c}，模式串T = { a, b, d } ，请找到模式串在主串中第一次出现的位置。 提示: 不需要考虑字符串大小写问题, 字符均为小写字母。

一、BF算法

Brute-Force算法，又称蛮力算法、暴风算法，简称BF算法。它是一种比较简单的字符串匹配算法，也正是因为其简单易用性，所以该算法也是在日常开发中最常见的字符串匹配算法。

思路如下：

（1）分别利用计数指针i和j指示主串OriginalString和模式串matchString中当前正在比较的字符位置，二者的初始值均设置为1

（2）如果主串和模式串均尚未比较到串尾，即i和j均小于等于originalString和matchString的长度时，则循环执行以下的操作:

① OriginalString[i]和matchString[j]比较，若相等，则i 和 j分别指示对应串中下一个位置，然后继续比较后续的字符;

② 若不相等，指针后退重新开始匹配，从主串的下一个字符(i = i - j + 2)起再重新和模式串第一个字符(j = 1)比较;

（3）上述遍历匹配完了之后，如果j > matchString.length，说明模式串matchString中的每个字符依次和主串originalString中的一个连续字符序列相等，则匹配成功，返回和模式串matchString中第一个字符在主串originalString中的序号(i-matchString.length)；否则匹配失败，返回-1。

代码如下：

#include <stdio.h>
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define Max_Size 40 // 字符数组的初始大小

// 字符串类型
typedef char String[Max_Size + 1]; // 第0号位置存储字符串的长度

// 操作的状态
typedef enum : int {
  Success,
  Error,
} Status;

// 将字符数组转换成一个字符串
Status transferCharsToString(String string, char *chars) {
  if (strlen(chars) > Max_Size) {
    return Error;
  }

  string[0] = strlen(chars); // 字符串的第0号位置存储字符串的长度
  // 将chars数组中的字符依次放入string中（从string的第一个位置开始存）
  for (int i = 1; i <= string[0]; i++) {
    string[i] = *(chars + i - 1);
  }
  return Success;
}

// 清除字符串
Status clearString(String string) {
  string[0] = 0; // 令字符串长度为0即可
  return Success;
}

// 打印字符串
void printString(String string) {
  printf("当前的字符串为：");
  for (int i = 1; i <= string[0]; i++) {
    printf("%c", string[i]);
  }
  printf("\n");
}

int match(String originalString, String matchString) {
  // 首先获取到原始字符串和匹配字符串的长度
  int originalLength = originalString[0];
  int matchLength = matchString[0];

  // 分别使用i和j来表示原始字符串和模式字符串的遍历坐标
  int i = 1;
  int j = 1;

  // 逐个匹配
  while (i <= originalLength && j <= matchLength) {
    if (originalString[i] == matchString[j]) {
      i++;
      j++;
    } else {
      // 指针回溯，重新匹配
      i = i - j + 2; // 原始字符串回退到开始遍历位置的下一个位置
      j = 1; // 模式匹配字符串回退到初始位置
    }
  }

  // 判断是否匹配成功
  if (j > matchLength) {
    // 匹配成功
    return i - j + 1;
  }

  // 匹配不成功
  return -1;
}

int main(int argc, const char * argv[]) {

  String string;
  transferCharsToString(string, "sarfsgglikhjffgdskjdfgdskjgh");
  printString(string);

  String matchString;
  transferCharsToString(matchString, "lik");
  printString(matchString);

  printf("i = %d\n", match(string, matchString));

  return 0;
}

该算法的时间复杂度是：O(n*m)。

BF算法有一个弊端，如下如所示：

主串有50个字符，前49个都是0，最后一个是1；模式串有10个字符，前9个都是0，最后一个是1。此时如果使用BF算法进行匹配的话，那么就会导致每一次匹配都会差那么一丢丢，也就会导致很多无效的重复匹配。接下来我们就来看一下如何解决这个问题。

二、RK算法

RK算法，是由Rabin和Karp这两个人共同提出的一个算法。

RK算法的核心思路如下：

（1）两个数字的比较比两个字母的比较要容易，所以RK算法比较的是数字。

（2）RK算法中需要使用哈希算法来对对应的字符串进行哈希运算，最后求得一个数值。

（3）将主串拆解成与模式串长度相等的若干个子串，然后通过比较子串与模式串的哈希值来确定二者是否相等

（4）需要注意的是，不要将子串事先都先拆分出来，然后换算成哈希值存到一个数组里面，在比较的时候从数组中取出对应的哈希值进行比较，不要这样去做；而是一边拆分一边比较。

（5）Hash，一般中文翻译成“散列”，也会音译成“哈希”。Hash在开发中是很常见的，比如我们常用的MD5算法就是Hash算法。我们需要设计一个哈希公式，来完成字母到数字的映射，设计的这个哈希算法要尽可能简单并且尽可能不会有哈希冲突。

657 = 6*10^2 + 5*10^1 + 7*10^0。10是十进制的进位

字母也可以参照上面的那种方式来转换成数字，如下：

cda = (c-a)*26^2 + (d-a)*26^1 + (a-a)*26^0 = 1430。由于字符均为小写字母，而小写字母共有26个，所以这里的进制是26进制。

这样的话，就可以将cda这个字符串给转换成数字1430了，然后就可以通过数字进行比较了，而不必再通过一个一个的字符进行对比比较了。

（6）相邻的两个子串S[i]和S[i+1]（S指的是主串的地址，i表示子串在主串中的起始位置，子串的长度等于模式串的长度m）对应的哈希值计算公式有交集，也就是说，我们可以使用S[i]来计算出S[i+1]的哈希值。

实际上，S[i+1]是上一个S[i]去掉最高位数据之后其余的m-1位字符乘以26进制再加上最后一个字符得到。换算成公式如下：

St[i+1] = (St[i] - d^2 * (S[i] - ‘a’)) * d + (S[i + m] - ‘a’)

（7）因为我们这里使用的是哈希值来比较两个字符串是否相等，但凡是使用哈希算法，就不可避免地有一个问题，那就是哈希冲突。解决哈希冲突有两种方式，第一种就是设计更为复杂的哈希公式，而在该场景下，为了实现一个字符串的匹配算法，实际上是没有必要采用非常复杂的哈希公式的；第二种解决哈希冲突的方式就是，如果相等的时候，不要直接返回结果，而是进行二次确认。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define twentySixDecimal 26 // 26进制

// 用于再次确认字符串是否真正匹配
bool isTruelyMatched(char *mainString, int index, char *matchString) {
  int matchLength = (int)strlen(matchString);
  for (int i = index; i < index + matchLength; i++) {
    if (mainString[i] != matchString[i - index]) {
      return false;
    }
  }
  return true;
}

int rkMatch(char *mainString, char *matchString) {
  // 主串和模式串的长度
  long mainLength = strlen(mainString);
  long matchLength = strlen(matchString);

  // 最高次幂系数（用于计算下一个子串的哈希值的时候移除上一个子串的最高次幂项）
  int maxPowerCoefficient = 1;

  // 模式串和子串的哈希值
  int matchStringHash = 0;
  int subStringHash = 0;
  for (int i = 0; i < matchLength; i++) {
    maxPowerCoefficient = i > 0 ? twentySixDecimal * maxPowerCoefficient : 1; // 最高次幂系数
    matchStringHash = matchStringHash * twentySixDecimal + (matchString[i] - 'a'); // 模式串的哈希值
    subStringHash = subStringHash * twentySixDecimal + (mainString[i] - 'a'); // 第一个子串的哈希值
  }

  // 依次遍历匹配子串和模式串
  for (int i = 0; i <= mainLength - matchLength; i++) {
    // 匹配上了，则返回对应的坐标
    if (subStringHash == matchStringHash) {
      // 为了解决哈希冲突，需要二次确认
      if (isTruelyMatched(mainString, i, matchString)) {
        return i;
      }
    }

    // 没有匹配上，则计算下一个子串的哈希值
    subStringHash = (subStringHash - (mainString[i] - 'a') * maxPowerCoefficient) * twentySixDecimal + (mainString[i + matchLength] - 'a');
  }

  return -1;
}



int main(int argc, const char * argv[]) {

  printf("%d\n", rkMatch("asdfghjk", "ghuj"));

  return 0;
}

三、KMP算法

KMP算法，是由D.E.Knuth、J.H.Morrs和VR.Pratt共同发表的一个字符串模式匹配算法，该算法可以大大避免重复遍历的情况。

1，KMP算法的原理

（1）情况一

假设现在有一个主串S=“abcdefgab”，模式串T=“abcdex”，可以看到，前5个字母都是相等的，后面的第6个字母’f’和’x’是不相等的，如下图所示：

接下来，如果是按照BF算法的话，那么就需要执行下面的②③④⑤的过程：

按照BF算法的设计，其执行过程就是上面这样。现在我们分析一下，模式串T=“abcdex”中，首字母a与剩下串”bcdex”中的任一字符都不相等，而在上面的①中，主串S与模式串T中的前5个字符都是匹配相等的，这也就意味着，模式串中的第一个字符a与主串中的第2~5个字符都是不相等的，所以上面的②③④⑤这4个步骤其实都是多余的。

KMP算法的思想就是，设法利用这些已知信息，不要将位置回溯到已经比较过的位置，而是尽可能回溯到后面的位置，这样就能提高算法的效率。

现在主串S和模式串T均不变，我们看一下KMP算法是如何分析的。

如上图，我们此时已经知道，在模式串T中，第一位字符a与后面的字符串中的所有字符均不相等（注意这是前提条件，至于如何判断，后面会有说明）。

模式串T的第2位字符b与主串S的第2位字符b在第①步已经判断相等了，那么这就意味着，T串中的首字符a与主串S中的第2位字符b是不需要判断的，因为我们知道它俩肯定不可能相等，因此上面的第②步是可以省略的。如下图：

同样的道理，在我们知道模式串T中的首字母a与剩下的字符串中的任意字符均不相等的前提下，模式串T中的首字母a与主串S中的’c’、’d’、’e’也都可以在上面的第①步之后就确定是不相等的，因此后面的②③④⑤步就都是不必要的，可以省略，因此，只保留①和⑥即可，如下图：

之所以会保留第⑥步，是因为我们事先已经知道了T[1]!=T[6]，而通过第①步又确定了T[6]!=S[6]，那么通过这俩条件是不可以判断出T[1]!=S[6]的，因此需要重新比较T[1]和S[6]，所以需要保留第⑥步。

（2）情况二

假设现在有一个主串S=“abcababca”，模式串T=“abcabx”。

对于一开始的第一次判断，前五个字符完全相等，第六个字符不相等，如下图所示：

根据刚才的经验，模式串T的首字母a与T的第2位字母b、T的第3位字母c都是不相等的，因此T的首字母a就不需要与S的第2位、S的第3位进行比较了，所以下面的第②③步就都是多余的了：

由于模式串T的第1、2位分别与模式串T的第4、5位相等，而在第①次比较的时候，模式串T中的第4、5位与主串S中的第4、5位已经比较过了是相等的，因此可以断定，模式串T中的第1、2位与主串S中的第4、5位是相等的，所以下面的第④⑤步的比较也是多余的:

也就是说，如果子串中存在着与首字符相等的字符，那么也是可以省略一些不必要的判断步骤的。

如下图所示，就是省略了模式串的前两位a和b与主串S中的4、5位置的字符的匹配操作：

通过上面的这两个例子，我们可以看到，在BF算法流程中，主串S中的i值是需要不断回溯的；而在KMP算法的流程中，在省略了不必要的判断流程之后，主串S中的i值不会回溯，也就是说，主串S中的i值是不会变小的。

实际上，KMP算法的核心就是避免让不必要的回溯发生。

既然在KMP算法中，主串S中的i值是不可能回溯的，那我们就要考虑会更改模式串中的j值。

那么j值的变化有什么规律呢？在上面的分析中，确定模式串T的j值回溯的位置的时候，我们屡次提到模式串T的首字符与自身后面字符的比较。当模式串T的首字符与自身后面字符均不相等的时候，j值始终是回溯到1的位置；而当模式串T的首字符与自身后面字符有部分相等的时候，那么j的取值就会不一样。由此可知，模式串T的回溯位置j的变化与主串S没有多大关系，而与模式串T的结构中是否有重复字符有很大关系。

在上面第一种情况中，模式串T=“abcdex”中，无重复字符，因此j回溯到了1的位置：

而在上面的第二种情况中，模式串T=“abcabx”中，前缀ab与后面的字符x之前的ab是相等的，因此j回溯到了3的位置：

所以我们可以得出规律：模式串的回溯位置j值的大小取决于当前字符之前的子串的前后缀的相似程度。

我们可以定义一个数组next，用于记录模式串T的各个位置上的回溯地址j值的变化，next数组的长度就是模式串T的长度，于是我们可以得出下面函数的定义：

2，next数组值的推导

（1）情况一——模式串中无任何重复字符

如上图，模式串T=“abcdex”。

• 当j = 1时，next[1] = 0；
• 当j = 2时，由1到j-1范围内有字符”a”，不存在相等的字符，属于其他情况，next[2] = 1；
• 当j = 3时，由1到j-1范围内有字符”ab”，不存在相等的字符，属于其他情况，next[3] = 1；
• 当j = 4时，由1到j-1范围内有字符”abc”，不存在相等的字符，属于其他情况，next[4] = 1；
• 当j = 5时，由1到j-1范围内有字符”abcd”，不存在相等的字符，属于其他情况，next[5] = 1；
• 当j = 6时，由1到j-1范围内有字符”abcde”，不存在相等的字符，属于其他情况，next[6] = 1；

在该例中，模式串T=“abcdex”中不存在任何重复字符，此时next数组的各元素取值的推演过程符合公式中的第一种情况和第三种情况。

next数组 = {0,1,1,1,1,1}。

（2）情况二——模式串类似于“abcabx”

如上图，模式串T = “abcabx”。

• 当j = 1时，next[1] = 0；
• 当j = 2时，由1到j-1范围内有字符”a”，不存在相等的字符，属于其他情况，next[2] = 1；
• 当j = 3时，由1到j-1范围内有字符”ab”，不存在相等的字符，属于其他情况，next[3] = 1；
• 当j = 4时，由1到j-1范围内有字符”abc”，不存在相等的字符，属于其他情况，next[4] = 1；
• 当j = 5时，由1到j-1范围内有字符”abca”，此时前置“a”与后缀”a”相等，属于第二种情况，P[1, 2-1] == P[5-2+1, 5-1]，即p[1] == p[4]，由此推断出k = 2，所以next[5] = 2；
• 当j = 6时，由1到j-1范围内有字符”abcab”，此时前缀“ab”与后缀“ab”相等，属于第二种情况，p[1, 3-1] == p[6-3+1, 6-1]，即p[1, 2] == p[4, 5]，由此推断出k = 3，所以next[6] = 3。

根据上面的分析其实可以得出一个结论，如果前后缀1个字符相等，k = 2；前后缀2个字符相等，k = 3；前后缀n个字符相等，k = n+1。

（3）情况三——模式串类似于“ababaaaba”

如上图，模式串T = “ababaaaba”。

• 当j = 1时，next[1] = 0；
• 当j = 2时，由1到j-1范围内有字符”a”，不存在相等的字符，属于其他情况，next[2] = 1；
• 当j = 3时，由1到j-1范围内有字符”ab”，不存在相等的字符，属于其他情况，next[3] = 1；
• 当j = 4时，由1到j-1范围内有字符”aba”，此时前置“a”与后缀”a”相等，属于第二种情况，前后缀有1个字符相等，k = 2，所以next[4] = 2；
• 当j = 5时，由1到j-1范围内有字符”abab”，此时前置“ab”与后缀”ab”相等，属于第二种情况，前后缀有2个字符相等，k = 3，所以next[5] = 3；
• 当j = 6时，由1到j-1范围内有字符”ababa”，此时前置“aba”与后缀”aba”相等，属于第二种情况，前后缀有3个字符相等，k = 4，所以next[6] = 4；
• 当j = 7时，由1到j-1范围内有字符”ababaa”，此时前置“a”与后缀”a”相等，属于第二种情况，前后缀有1个字符相等，k = 2，所以next[7] = 2；
• 当j = 8时，由1到j-1范围内有字符”ababaaa”，此时前置“a”与后缀”a”相等，属于第二种情况，前后缀有1个字符相等，k = 2，所以next[8] = 2；
• 当j = 9时，由1到j-1范围内有字符”ababaaab”，此时前置“ab”与后缀”ab”相等，属于第二种情况，前后缀有2个字符相等，k = 3，所以next[9] = 3；

这个例子中，我是直接通过前后缀相等字符的个数来推断出k值的，k值 = 前后缀相等字符的个数 + 1。

同时需要特别声明的一点是，next数组比较的是连续的前缀字符和后缀字符。例如当j=6时，字符串是”ababa”，此时的前缀是“aba”，后缀也是”aba”；当j=7时，字符串是“ababaa”，此时的前缀是“a”，后缀也是“a”，不要误以为是“ab”。

（4）情况四——模式串类似于“aaaaaaaab”

如上图，模式串T = “aaaaaaaab”。

• 当j = 1时，next[1] = 0；
• 当j = 2时，由1到j-1范围内有字符”a”，不存在相等的字符，属于其他情况，next[2] = 1；
• 当j = 3时，由1到j-1范围内有字符”aa”，此时前置“a”与后缀”a”相等，属于第二种情况，前后缀有1个字符相等，k = 2，所以next[3] = 2；
• 当j = 4时，由1到j-1范围内有字符”aaa”，此时前置“aa”与后缀”aa”相等，属于第二种情况，前后缀有2个字符相等，k = 3，所以next[4] = 3；
• 当j = 5时，由1到j-1范围内有字符”aaaa”，此时前置“aaa”与后缀”aaa”相等，属于第二种情况，前后缀有3个字符相等，k = 4，所以next[5] = 4；
• 当j = 6时，由1到j-1范围内有字符”aaaaa”，此时前置“aaaa”与后缀”aaaa”相等，属于第二种情况，前后缀有4个字符相等，k = 5，所以next[6] = 5；
• 当j = 7时，由1到j-1范围内有字符”aaaaaa”，此时前置“aaaaa”与后缀”aaaaa”相等，属于第二种情况，前后缀有5个字符相等，k = 6，所以next[7] = 6；
• 当j = 8时，由1到j-1范围内有字符”aaaaaaa”，此时前置“aaaaaa”与后缀”aaaaaa”相等，属于第二种情况，前后缀有6个字符相等，k = 7，所以next[8] = 7；
• 当j = 9时，由1到j-1范围内有字符”aaaaaaaa”，此时前置“aaaaaaa”与后缀”aaaaaaa”相等，属于第二种情况，前后缀有7个字符相等，k = 8，所以next[9] = 8；

这种情况下，注意前后缀字符的长度最多是原字符串长度-1，也就是说，相等的前后缀字符串长度必须要小于原字符串长度。

3，next数组值的代码求解

上面👆第2步，我们介绍了next数组的各元素取值推导逻辑，接下来我们就来介绍一下如何在代码层面去计算得出next数组的各个元素值。

先来说一下结论。在求解next数组的时候，一共就4种情形：

①next[1] = 0

②当i==0时，表示需要重新开始新一轮的比较，因此i++，j++，next[j] = i

③当模式串T[i] == T[j]时，i++，j++，next[j] = i

④当模式串T[i] != T[j]时，i值扩大比较范围而回溯，所以i = next[i]。

求解next数组的代码的逻辑过程如下：

①首先设置next[1] = 0；

②设置两个索引下标，i = 0，j = 1，i用于求解回溯的地址，j用于遍历模式串

③循环遍历模式串，在每一次循环遍历体中都执行如下④⑤⑥条件语句

④如果i==0，则i++，j++，next[j]=i

⑤如果i!=0并且T[i] == T[j]，则i++，j++，next[j] = i

⑥如果i!=0并且T[i] != T[j]，则指针回溯，i = next[i]

接下来我们通过图例来分析一下next数组的代码求解过程。

本例中，主串S=“abcababca”，模式串T=“abcdex”。

在最一开始，设置next[1] = 0，并且初始化两个变量i = 0，j = 1。

此时遍历的时候发现，i == 0，那么i++，j++，并且将next[j] = i，一顿操作之后，i == 1，j == 2，next[2] == 1，如下图：

然后进入下一次遍历，此时T[i] = T[1] = a，T[j] = T[2] = b，所以T[i] != T[j]，因此i需要回溯，i = next[i] = next[1] = 0，如下图：

然后进入下一层遍历，此时i == 0，那么i++，j++，并且将next[j] = i，一顿操作之后，i == 1，j == 3，next[3] == 1，如下图：

然后进入下一次遍历，此时T[i] = T[1] = a，T[j] = T[3] = c，所以T[i] != T[j]，因此i需要回溯，i = next[i] = next[1] = 0，如下图：

然后进入下一层遍历，此时i == 0，那么i++，j++，并且将next[j] = i，一顿操作之后，i == 1，j == 4，next[4] == 1，如下图：

然后进入下一次遍历，此时T[i] = T[1] = a，T[j] = T[4] = d，所以T[i] != T[j]，因此i需要回溯，i = next[i] = next[1] = 0，如下图：

然后进入下一层遍历，此时i == 0，那么i++，j++，并且将next[j] = i，一顿操作之后，i == 1，j == 5，next[5] == 1，如下图：

然后进入下一次遍历，此时T[i] = T[1] = a，T[j] = T[5] = e，所以T[i] != T[j]，因此i需要回溯，i = next[i] = next[1] = 0，如下图：

然后进入下一层遍历，此时i == 0，那么i++，j++，并且将next[j] = i，一顿操作之后，i == 1，j == 6，next[6] == 1，如下图：

此时，j == 6，即j == T.length，满足循环退出条件，退出循环。

代码如下：

void getNext(char *string, int *next) {
  int stringLength = (int)strlen(string);
  int i = 0, j = 1;
  next[1] = 0;
  
  while (j <= stringLength) {
    if (i == 0) {
      i++;
      j++;
      next[j] = i;
      continue;
    }
    
    if (string[i] == string[j]) {
      i++;
      j++;
      next[j] = i;
    } else {
      // 指针回溯
      i = next[i];
    }
  }
}

4，KMP算法代码求解

现在我们已经计算出next数组了，我们知道，next数组是用于模式串中的指针回溯的，那么如何将next数组应用到KMP算法中呢？

现在主串S = “abcababca”，模式串T = “abcdex”。

我们通过一个while循环来双层遍历，通过i和j来分别记录主串和模式串的遍历到的索引下标，遍历结束的条件是i超过主串长度或者j超过模式串长度。

如果是采用BF算法的话，当字符不匹配的时候，模式串的索引j会回退到初始位置1，主串的索引下标会回退到本次遍历开始时的主串位置的下一个位置，如下图所示：

但是如果是采用KMP算法的话，在i = 4，j = 4的时候发现不匹配，那么此时主串中的索引i是不需要回退的，模式串中的索引j需要回退到next[j]的位置。此时发现next[j]（即next[4]）=1，那么就从模式串的第1个位置开始新一轮的遍历。

具体代码如下：

void getNext(char *string, int *next) {
  int stringLength = (int)strlen(string);
  int i = 0, j = 1;
  next[1] = 0;
  
  while (j <= stringLength) {
    if (i == 0) {
      i++;
      j++;
      next[j] = i;
      continue;
    }
    
    if (string[i] == string[j]) {
      i++;
      j++;
      next[j] = i;
    } else {
      // 指针回溯
      i = next[i];
    }
  }
}

int kmpMatch(char *S, char *T) {
  // 主串和模式串的长度
  int SLength = (int)strlen(S);
  int TLength = (int)strlen(T);
  
  // 计算模式串T的回溯数组
  int *next = malloc(sizeof(int) * (TLength + 1));
  getNext(T, next);
  
  // 遍历比较主串和模式串
  int i = 1; // 主串索引
  int j = 1; // 模式串索引
  while (i <= SLength && j<=TLength) {
    if (j == 0 || S[i-1] == T[j-1]) { // j==0表示第一个字符就匹配失败了之后的情况
      i++;
      j++;
      continue;
    }
    
    j = next[j];
  }
  
  // 核验是否匹配成功
  if (j > TLength) {
    return i - j + 1;
  }
  return -1;
}

以上。