字符串

字符串是由字符按顺序排列形成的串结构，在 ACM 中会用到两种字符串定义方式：

// C-style string
#define STR_LEN 100
char s1[STR_LEN];

// C++/STL-style string
#include <string>
std::string s2;

C 风格字符串本质上就是 字符数组；C++/STL 风格字符串是将 字符数组与其操作抽象集成形成的类，可以说本质上依旧是对字符数组进行操作。

字符串的常用操作

对于 C 风格字符串而言，所有的字符串操作函数被定义在头文件 cstring 中，在使用时需要在程序中添加 #include<cstring>。

// Index
char a = s1[1];

// Get length -> O(n)
int b = strlen(s1);

// Compare
int c = strcmp(s1, s2);

// Memory set value
memset(s1, 0, sizeof(s1));

对于 C++/STL 风格的字符串而言，其字符串类定义在头文件 string 中，在使用时需要在程序中添加 #include<string>。

// Index
char a = s1[1];

// Get length -> O(1)
int b = s1.length();

// Compare
bool c = s1 < s2;

字符串匹配

字符串匹配就是在一个字符串中寻找另一个字符串的过程，字符串匹配在计算机领域有非常多的应用（搜索引擎、数据库等），其重要程度也不言而喻。

在如下例子中 s1 是 s2 的一个匹配，而s3不能匹配其他两个字符串：

s1 = "abc";
s2 = "aaabccc";
s3 = "ac";

匹配算法

由于在 C 标准函数中没有提供对于任意起始位置寻找匹配的方法（C++/STL 提供了 find 方法，但是 $O(n^2)$ 复杂度），所以我们一般需要自己实现匹配算法。

在匹配算法中，我们将用于匹配的字符串称为 模式串，被匹配的字符串称为 匹配串，还是上面那个例子，用 s1 和 s2 去匹配，则 s1 是模式串，s2 是匹配串。

暴力匹配

我们很容易能够想到暴力方法实现字符串匹配：

// s1: Match string
// s2: Pattern string
int match(const char s1[], const char s2[]) {
  // Get length
  int l1 = strlen(s1), l2 = strlen(s2);

  // i: Start position of match string
  // lmt: Max posible start position
  for (int i = 0, lmt = l1 - l2; i <= lmt; ++i) {
    // Match flag
    bool f = true;

    // Scanning pattern string
    for (int j = 0; j < l2; ++j)
      if (s1[i + j] != s2[j]) {
        f = false;
        break;
      }

    // Check if matched, then return position
    if (f)
      return i;
  }

  // Not found
  return -1;
}

非常简单明了，就是 $O(n^2)$ 的时间复杂度实在是有点不敢恭维了。

接下来我们来看看这样一个例子：

s1 = "abad";
s2 = "abacbcdhijk";

s1 作为模式串，s2 作为匹配串，来跑一下暴力算法：

一开始是这样的：

我们看到此时 s1[i + j] 和 s2[j] 此时一样，所以 j 会往后走：

接下来两步显然都能匹配，所以我们快进到第三步：

此时发生了 失配，所以根据暴力算法，我们移动 i，复位 j：

但是实际上这样真的好吗？我们发现 s2 在从 b 开始时，很明显不可能匹配，因为 s1 的开头是 a，所以更好的移动方法应该是把 j 移动到 1，把 i 移动到 2，因为 两个起始位置的a已经可以匹配了：

我们看见此时虽然 i 和 j 变了，但是 i+j 并没有改变，而像这样子的例子其实还有很多，比如下面这个：

如果按照暴力算法来，那么下一步会变成这样：

但是更好的方法其实应该这样：

同样，还是 i 和 j 改变了，i+j 没有变。

那么这时候我们可以完全不需要 i 这个变量了，把 i+j 给定义成一个新的变量 k，因为如果按照我们想出的这个跳转方法来看，k 一定是 递增 的，那么接下来就是怎么处理 j 的跳转和 k 在什么情况下会递增了。

万幸的是，已经有前人把这种思想变成了一个著名算法 —— KMP。

KMP 算法

KMP 算法由 D.E.Knuth、J.H.Morris 和 V.R.Pratt 提出的，KMP 取的就是他们名字的首字母。

在 KMP 算法中，核心思想是 next[i] 数组。

next[i] 数组定义为：在字符串 s[0..i-1] 中 最大的公共真前后缀长度。

这里需要说明，一个字符串的 真 前后缀是 不包括 这个字符串本身的。

用上面的一个例子：

由于 i 为 0 时，字符串 s[0..i-1] 不存在，所以定义 next[0] 为 -1。

i 为 1 时，字符串 a 的真前后缀都是空串，所以 next[1] 为 0。

i 为 2 时，字符串 ab 的真前缀为 ∅、a，真后缀为 ∅、b，所以最长的公共前后缀依然是空串，所以 next[2] 为 0。

i 为 4 时，字符串 abab 的真前缀为 ∅、a、ab、aba，真后缀为 ∅、b、ab、bab，所以最长的公共前后缀为 ab，所以 next[4] 为 2。

那么这个数组有啥用呢？我们再把上面的例子搬下来，但这次我们把 next 数组一起弄上去：

下一步：

看！在发生失配之后，j 就被赋值成了 next[j]。
所以 next 数组就是帮助 j 进行跳转的。

那么如何计算 next 数组呢？其实非常简单：

// const char s[]: Pattern string
// int next: Next array
void getNext(const char s[], int next[]) {
  // s[0..-1] not exists, so assign next[0] to -1
  next[0] = -1;

  // Find next
  for (int i = 0, j = -1; s[i];)
    if(j == -1 || s[i] == s[j]) {
      ++i;
      ++j;
      next[i] = j;
    }
    else 
      j = next[j];
}

需要注意的是，我们如果要使用 next 数组，一定是使用模式串的 next 数组。

这个代码实在是非常简单，我们来一步一步演算一下：

一开始的状态如上，要注意的是 j 此时为 -1，其表示 next[0]。

由于 j 为 -1，所以下一步 i 和 j 都要向后推进，并置 next[1] 为 0，此时才开始正式比较：

此时 i 和 j 所指向的字符不同，让 j 赋值为 next[j]：

然后又是推进 i 和 j：

接下来比较 i 和 j 指向的字符，他们相等，所以继续推进并修改 next 数组：

i 和 j 指向字符依然相等，继续：

这里又不相等了，所以回退 j 为 next[j]：

仍然不相等，继续回退：

此时 j 为 -1 了，所以到了最后一步：

至此，算法模拟完毕。

经过观察不难看出，i 和 j 其实指示的是一个 可能的相同前后缀的结束位置。

我们只要指定了这两个位置，就可以同时推进 i 和 j 来检查前后缀是否相等，如果遇到了不相等的情况，那么显然这个 最长的长度就是 j，表明 s[0..j-1] 这个前缀和 s[i-j+1..i-1] 这个后缀是相等的，且长度为 j。

那么当 i 和 j 失配的时候，为什么要让 j 等于 next[j] 来跳转呢？

因为当前的前后缀可能已经不能继续扩展下去了，但是我们利用 next[j] 可以找到之前已经发现的公共前缀来继续匹配，我们举一个例子：

这里我们试图匹配的前缀和后缀分别是 abab 和 abac，明显无法匹配，所以我们跳转 j：

而这里就变成了我们需要试图匹配的前后缀分别为 ab 和 ac，我们之间跳过了一个 a 和 a 的匹配，因为我们通过 next 数组已经知道了他们是一样的，所以我们可以直接快进到 ab 和 ac 的匹配。

也就是说，这种操作其实类似于试图把一个前缀“续上”，这样子可以利用已知信息来更新最大长度。

那么知道了 next 数组，那么按照我们之前发现的匹配方法，就能得到如下代码：

// const char s1[]: Match string
// const char s2[]: Pattern string
// int next[]: Next array
int match(const char s1[], const char s2[], int next[]) {
  for (int i = 0, j = 0; s1[i];)
    if (j == -1 || s1[i] == s2[j]) {
      ++i;
      ++j;

      // If matched, then return position
      if (!s2[j])
        return i - strlen(s2);
    }
    else 
      j = next[j];

  // Not matched
  return -1;
}

模拟演算就不做了，匹配函数和求 next 函数看起来其实很像，你甚至可以认为求 next 本质上就是 模式串自己在和自己做匹配，即找相同前后缀。

KMP 算法比暴力算法已经不知道高到哪里去了，它的时间复杂度为 $O(n+m)$，其中 n 和 m 分别为匹配串和模式串的长度。

优化 KMP

朴素的 KMP 已经能做到很优了，所以再怎么优化也仅仅是停留在常数上了，这就出现了 KMP 的一种优化写法，这种优化主要体现在 next 数组的不同上，我们先来看看优化的写法：

// const char s[]: Pattern string
// int next[]: Next array
void getNext(const char s[], int next[]) {
  next[0] = -1;
  for (int i = 0, j = -1; s[i];)
    if (j == -1 || s[i] == s[j]) {
      ++i;
      ++j;
      // ==== Not optimized ====
      // next[i] = j
      // =======================
      next[i] = (s[i] == s[j] ? next[j] : j);
    }
    else 
      j = next[j];
}

我们看到，优化过后主要就是内部修改 next 数组的部分被换成了一个三目表达式，这个表达式等同于：

if (s[i] == s[j])
  next[i] = next[j];
else 
  next[i] = j;

为啥这么改呢？我们来看看例子：

next_pure 是没有优化的 next 数组，next_optimized 是优化过的 next 数组，乍一看感觉多了很多 -1，但是这正是关键所在，我们来用 aaaad 去匹配 aaaac 看看。

如果使用未优化的 next 数组，算法会这样走：

第一到四步：

我们在第五步发生了失配：

这时我们 j 就要回退了，接下来几步是这样的：

我们发现最后 j 退回到了 -1，因为无论如何匹配，a 前缀都无法接到 c 上，既然如此，那么何不把这些完全没有匹配可能的位置干脆全部置为 -1，这样一步就可以到了。

所以这就是 KMP 的优化（常数）写法，但是需要注意的是，如果采用了这种优化写法，那么 KMP 算法只能用来完成字符串匹配的工作了，因为我们把 next 数组的意义给改变了，导致一些本来可以利用 next 数组性质解决的问题变得不可解。

KMP 另类应用

KMP 算法不仅仅可以用来字符串匹配，它还有一些另类应用，但是这些其实都是基于 next 数组的，也就是在以下的应用场景中，你不能使用 KMP 优化算法。

公共前后缀问题

有些问题需要使用公共前后缀长度，这一类问题基本上按照 next 数组的定义来解决就可以了，故不多赘述。

循环子串问题

next 数组有一个非常特殊的性质：

假设字符串长度为 len，则 len-next[len] 为一个 可能的 最小循环长度，如果要形成循环，那么需要 当且仅当 len 可以被 len-next[len] 整除时，即 len % (len - next[len] == 0，循环成立，且 最大 循环数量为 len / (len - next[len])，而这个最小的循环节为 s[0..len-next[len]-1]。

我们可以简单证明一下这个式子的正确性：

假设有字符串 S[0..7]，且已知 next[8] 为 6，所以由 next 定义可知子串 S[0..5] 和 S[2..7] 是一样的。

计算 len-next[len] 得 2，且 8 可以被 2 整除，所以最小循环节应该为 S[0..1]。

又由子串 S[0..5] 和 S[2..7] 相同，故可以得出 S[0..1] 和 S[2..3] 相同，S[2..3] 和 S[4..5] 相同，S[4..5] 和 S[6..7] 相同，故证。

参考例题