前言

已经毕业的神秘老学长将一块硬盘塞给了你，里面存储着近10年的期末考试原卷！但是很可惜，文件被加密了，只有输入正确的密码才能查看学习资料。硬盘中只有另外两个.txt文件，分别存有两个字符串，其中一个有足足2Mb大小！而另一个则是一个非常短的只有百来个字符的可爱小不点。

“找到所有的子串位置！”老学长的话语回荡在你的耳边，“将得到的结果连在一起便是学习资料的解压密码！”

怎么办！还有8个小时就要期末考试了，我们该如何拿到学习资料！

朴素匹配

一想到两个字符串进行模式匹配，那么我们脑海中蹦出来的第一个想法肯定是……

一个一个匹配！🤓☝️

将主串汇总所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。

这太简单了。假设我们有两个字符串abacccaaccba和ccb，我们想要找出主串中的所有ccb，我们可以把这个子串和主串从头开始一个一个匹配。

首先我们比较主串的前三个字符，即aba，很可惜，不是ccb；

接下来比较主串的第2个到第4个字符，是bac，很可惜，也不是ccb；

不过没关系，只要这样子一个一个匹配下去，我们总能匹配到。

一口气把代码写出来吧！

typedef struct {   // 定义串的结构体
	char ch[MaxLen]; // 存储串中字符的数组
  int length;      // 串的长度
}SString; 

int Index(SString S, SString T) {
  int i=1,j=1; // 初始化两个计数指针，i用于标注我们在比较主串的哪一个字符，j用于标注子串
  while(i<=S.length && j<=T.length) { // 在i和j没有超出各自串的范围时，循环
    if (S.ch[i]==T.ch[j]){ // 如果发现i和j各自指向的字符相同
      i++; j++;            // 那么i和j同时向后移动一个元素，开始比较各自串的下一个字符
    }
    else {                 // 如果两个字符不同
      i=i-j+2;             // i回到本次比较开始时的下一个字符，例如刚刚我们从主串的第1个元素开始匹配，i此时回到第二个元素
      j=1;                 // j回到子串的第一个元素
    }
  }
  if (j>T.length) return i-T.length; // 如果j大于子串的长度，即整个子串匹配成功，那么返回子串在主串中的位置
  return 0;  // 否则返回0，代表匹配失败
}

So Easy! 就在你准备快活地按下“编译并运行”时，你的直觉让你的指尖停了下来。

不对劲。

哦不对不对不对。不对！

用这种方法匹配子串和主串，假设主串长度为mm，子串长度为nn，那么在最坏的情况下，匹配完整个主串需要的时间是m×nm \times n！时间复杂度是O(mn)O(mn)！但是你只有8个小时的时间了，而你看完所有的卷子也需要至少7个半小时，这种方法显然不行。

那怎么办呢。

这时候就得请大名鼎鼎的KMP算法出场了。

KMP算法

1. 思路

我们可不可以想出一种方法，在匹配失败的时候不要直接将j指针归位到子串的最开始？

嘶……好像行得通，毕竟子串中会有重复的地方嘛，先拿个例子试试吧。

对于一个我们匹配到一半的模式串ababab??????和子串abababcdef。

当我们匹配到第7个元素时

      i
      ↓
ababab??????
abababcdef
      ↑
      j

假如说此时匹配失败了，按照朴素匹配的思想，我们需要吧i回退到模式串第2个位置，j回退到子串第1个位置。

但是这样太慢了。

让我们发动惊人的注意力。我们注意到子串的前6个字符是ababab它是由ab重复3次组成。

那么直觉上来看我们是不是可以直接这样：

      i
      ↓
ababab??????
  abababcdef
      ↑
      j

i保持不变，而j仅回退到第5个元素。显然，i不必再回溯，而j也不用每次都回到头，那匹配效率一下子高了一大截！

但是，我们怎么知道什么时候回到哪个地方？总不能每次瞅一眼然后告诉计算机该怎么走吧？

2. next数组

我们要把j应该回溯到的元素序号存在next数组内。

换句话说，我们事先计算好这样一个数组，假设在j匹配到子串第7个元素时匹配失败，我们只需要查看一下next数组，找到next[7]中的值，直接把j的值改为该值。

也就是说，我们只需要计算出，在当前元素之前的字符组成的串中。前多少个字符（前缀）和后多少个字符（后缀）相同。

》〉什么是前缀和后缀？〈《

  • 串的前缀：从串的第一个元素开始的子串，但是不能和主串一样长。例如abab的前缀可以是a、ab、aba，不能是abab。

  • 串的后缀：从串的最后一个元素开始的子串，但是不能和主串一样长。例如abab的后缀可以是b、ab、bab。

对于例子中的子串abababcdef，在我们匹配到第7个字符c时，在c之前的元素可以组成串ababab，并且易知前4个字符组成的前缀和后四个字符组成的后缀相同，都是abab，那么在第7个字符匹配失败时，我们仅须将j回溯到第4+14+1个位置。也就是从第5个字符继续匹配。

abababcdef
    ↑
    j

现在我们试着求这个子串的整个next数组吧～

对于第一个元素，我们发现它前面没有字符。那我们规定其对应的next[1]为0。这样方便在算法进行下一轮计算时直接进行++j操作，恰好从子串的第一个字符重新匹配。

对于第二个元素，它前面只有一个元素a，那么它没有前缀和后缀，下一次匹配时我们要从第一个字符开始匹配，我们记next[2]为0+1=1。

对于第三个元素，它前面的串为ab，从前数和从后数也都没有相同的钱后缀，下一次匹配我们仍然要从头开始，记next[3]=1。

对于第四个元素，前串为aba，我们发现有一个长度为1的前缀和长度为1的后缀相同，都是a，那么下一次我们可以直接从第2个字符开始匹配，记next[4]为1+1=2。

对于第五个元素，前串为abab，有长度为2的前缀后缀相同，都是ab，那么可以记next[5]为2+1=3。

对于第六个元素，前串为ababa，记next[6]=3+1=4。

到第八个元素，前串是abababc，此时没有前缀和后缀相同，那么记next[8]=0+1=1。

理解了吗？那我们上代码。

void GetNext(SString T, int next[]){
  int i = 1, j = 0; // 一切的最开始，我们将i和j初始化
  next[1] = 0; // 规定next数组的第一个元素为0
  while (i < T.length) { // 当i不超过串的总长时，循环
    if (j == 0 || T.ch[i] == T.ch[j]){ // 如果j为0，或者i和j所指向的两个元素相同时
      ++i; ++j;                        // i和j分别加1
      next[i] = j;                     // 将next数组中的第i个元素记为j
    }
    else j = next[j];                  // 如果不相同那么j回到当前元素记录的回溯位置
  }
}

你可以理解上述代码为，将子串和自己匹配，但开始时j比i小一位。

进入第一轮循环时，由于j为0，满足判断条件，i和j加1，并将next[i]（即next[2]）记为1。

  i
  ↓
 ababcdef
 ababcdef
 ↑
 j

紧接着进行第二次循环，此时i=2，j=1，且它们所指的元素不相等，不满足条件，那么j返回到next[1]，即第0位。

  i
  ↓
 ababcdef
 ababcdef
↑
j

进行第三次循环，j为0，那么i++; j++;，此时j=1，i=3，next[3]=1。

   i
   ↓
 ababcdef
 ababcdef
 ↑
 j

进行第四次循环，我们发现两个指针指向的元素相同，那么i++; j++;，此时j=2 i=4，next[4]=2。

    i
    ↓
 ababcdef
 ababcdef
  ↑
  j

以此类推，我们可以得到整个子串的next数组。

3. 代码

整理整理我们的思路，可以得到完整的代码

int IndexKMP(SString S, SString T, int next[]){
  int i=1,j=1; // 开始时i和j均指向第一个字符
  int next[T.length+1]; // 我们遵循大部分教材，next数组第一个元素为空，保证元素下标和为序相同
  GetNext(T, next); // 计算next数组
  while(i <= S.length && j <= T.length) { // 当i和j没有超过各自的串长时，循环
    if (j==0 || S.ch[i]==T.ch[j]){ // 如果j为0或者两个指针指向的字符相同
      ++i; ++j;                    // i和j都往后移一位
    }
    else j = next[j];              // 否则j回到next数组中记录的回溯位置
  }
  
  if (j>T.length) return i-T.length; // 如果j遍历完了子串，说明遍历成功，返回子串在主串中的位置
  return 0; // 否则返回0表示失败
}

void GetNext(SString T, int next[]){
  int i = 1, j = 0; // 将i和j初始化
  next[1] = 0; // 规定next数组的第一个元素为0
  while (i < T.length) { // 当i不超过串的总长时，循环
    if (j == 0 || T.ch[i] == T.ch[j]){ // 如果j为0，或者i和j所指向的两个元素相同时
      ++i; ++j;                        // i和j分别加1
      next[i] = j;                     // 将next数组中的第i个元素记为j
    }
    else j = next[j];                  // 如果不相同那么j回到当前元素记录的回溯位置
  }
}

4. KMP数组的优化

聪明的你一定发现了，目前这个算法并不是最优的……

干嘛这么惊恐地看着我(ﾟдﾟ≡ﾟдﾟ)，它的优化其实很简单，仅仅需要一个小巧思。

你看，对于abababcdef，它的next数组为：

next=[0,1,1,2,3,4,5,1,1,1]\boxed{\text{next}=[0,1,1,2,3,4,5,1,1,1]}

那么想想，如果我们匹配到第三个字符，发现不匹配，此时查询next[3]=1，我们需要回到第一个字符重新匹配，但是我们知道，第1个字符和第3个字符一样，第3个字符不匹配，那么第1个字符也必然不匹配，介时我们又要查表，跳转到next[1]=0。

那么我们为什么不能直接跳转到0呢？

没错，原始 KMP 在失配后，有时会跳到一个字符相同的位置，导致下一次比较必然再次失配。nextval 会直接跳过这种无效比较。

很简单吧？我们直接上代码。

void GetNextVal(SString T, int next[], int nextval[]) {
    nextval[1] = 0; // 同样，规定第一个元素为0

    for (int i = 2; i <= T.length; ++i) { // 从第二个元素依次检查
        int j = next[i];                  

        if (T.ch[i] != T.ch[j]) {         // 如果next数组中回溯的字符和该字符不相同
            nextval[i] = j;               // 则保持不变
        } else {
            nextval[i] = nextval[j];      // 否则第j个元素改为第i个元素
        }
    }
}

现在你已经熟练掌握KMP算法了，你可以得意洋洋的拿到密码了！

手机响了。已读不回了99+消息的老学长突然给你发了条信息。

“那个，忘了告诉你了，其实我的密码串是从序列0开始的，你需要把算法改成从0开始的版本哦。”

“千万不可以在return前直接减1，否则晚上会有一个大猛1来框框敲你宿舍门😠”

“我相信你一定能写出来。”

pasted-image-1782642667317.webp