欢迎各位道友来到数据结构第四章的内容，从这一章开始，算法大题的数量就会开始有大量的增长，因为很多经典的重要算法正是从这一章开始粉墨登场。所以说，这一章开始的内容会变得特别长，请大家耐心观看，并勤加练习。

串

小玄：烤牛肉串，烤羊肉串，烤猪肉串，烤干豆腐串~嘿嘿……哎哟，主人，你干嘛打人家啊！

（开窗户的声音）走你！（扔东西的声音）（越来越小的猫的嚎叫声）

概念

咳咳，这只捣乱的吃货猫猫已经被扔出去了。我们这里说的串不是上面那些给小玄馋成翘嘴儿的烧烤什么的，在数据结构中，串指的是字符串，就是由$0$个或多个字符组成的有限序列。通常记为：

$$ S = 'a_1a_2\cdots a_n' (n \ge 0) $$

其中，$S$是串名，单引号引起来的字符序列是串的值。$n$是串的长度，当$n =0$时，称串为空串。（由空格组成的串不是空串）

下面是一些相关的基础概念：

  • 子串：串中任意多个连续字符组成的子序列称为该串的子串。

  • 主串：包含该子串的串

  • 字符在串中的位置：该字符在串中的序号

  • 子串在主串中的位置：子串第一个字符在主串中的位置

  • 串的相等：两个串长度相等，且对应位置上字符完全相同

$\text{C/C++}$中的字符串

$C$语言中的字符串

纯$C$语言环境中如果你想表示一个字符串，必须使用$char$类型的指针或数组，且必须在末尾多留出一位\0结尾。由于$C$语言本身不提供对字符串的赋值，拼接，比较等操作，所以必须借助头文件<$string.h$>来实现。以下是该头文件中的常用函数

函数 功能 示例
strlen(s) 求字符串长度（不含'\0'） strlen("abc") → $3$
strcpy(dest, src) 字符串拷贝 strcpy(a, "hello")
strncpy(dest, src, n) 拷贝最多$n$个字符 更安全
strcat(dest, src) 字符串拼接 strcat(a, " world")
strncat(dest, src, n) 拼接最多$n$个字符  
strcmp(s1, s2) 字符串比较 返回$<0$、$0$、$>0$
strncmp(s1, s2, n) 比较前$n$个字符  
strchr(s, c) 查找字符首次出现 返回指针
strrchr(s, c) 查找字符最后一次出现  
strstr(s1, s2) 查找子串 返回指针
strtok(s, delim) 分割字符串 按分隔符切分
memset(ptr, val, n) 内存块填充 常用于初始化
memcpy(dest, src, n) 内存块拷贝 可拷贝任意类型
memmove(dest, src, n) 内存块移动（处理重叠）  
memcmp(p1, p2, n) 内存块比较  

这些函数都操作char*，需要你自己保证目标缓冲区足够大，否则会溢出（这是$C$字符串最大的安全隐患）。

$\text{C++}$中的字符串

在$C++$中，字符串定义在<$string$>头文件里，下面是这个头文件的常见用法：

#include <string>
using namespace std;

// 初始化和赋值
string s1;                  // 空字符串
string s2 = "hello";        // 用 C 字符串初始化
string s3("world");         // 同上
string s4(s2);              // 拷贝构造
string s5(5, 'a');          // "aaaaa"
string s6 = s2 + " " + s3;  // 拼接

// 容量操作
s.size();        // 返回字符个数，O(1)
s.length();      // 同 size()
s.empty();       // 是否为空，O(1)
s.capacity();    // 当前分配的内存能容纳多少字符
s.reserve(n);    // 预分配至少 n 个字符的空间，避免多次扩容
s.resize(n);     // 改变大小为 n，多出的字符默认 '\0'，少则截断
s.clear();       // 清空字符串，size 变为 0

// 访问元素
s[i];            // 下标访问，不检查越界，O(1)
s.at(i);         // 下标访问，越界抛 out_of_range 异常，O(1)
s.front();       // 第一个字符，O(1)
s.back();        // 最后一个字符，O(1)
s.data();        // 返回 C 风格字符串指针（C++11 起保证以 '\0' 结尾）
s.c_str();       // 返回 const char*，常用于C函数接口

// 修改操作
s += "abc";              // 追加字符串
s.append("def");         // 追加
s.push_back('x');        // 追加一个字符，O(1) 均摊
s.pop_back();            // 删除最后一个字符（C++11）
s.insert(pos, "str");    // 在 pos 处插入字符串，O(n)
s.erase(pos, len);       // 从 pos 开始删除 len 个字符，O(n)
s.replace(pos, len, "new"); // 替换子串
s.swap(s2);              // 交换两个字符串

// 查找子串和比较
s.find("abc");           // 查找子串首次出现位置，找不到返回 string::npos
s.rfind("abc");          // 从后往前找
s.find('x');             // 查找字符
s.substr(pos, len);      // 返回从 pos 开始长度为 len 的子串，O(len)
s.compare(s2);           // 比较，类似 strcmp，返回小于0, 0, 大于0

// 迭代器
s.begin();               // 指向首字符
s.end();                 // 指向尾后位置
s.rbegin();              // 反向迭代器
s.rend();
// 可用范围 for 遍历
for (char c : s) cout << c;

// 与C字符串和整数的类型转换
const char* p = s.c_str();          // string -> C 字符串
string s = "123";
int n = stoi(s);                    // string -> int
double d = stod(s);                 // string -> double
string s2 = to_string(456);         // 数值 -> string

那么这一章为了方便演示，我就用$\text{C++}$的<$string$>的串来写代码了。反正考研大题也不限制你用$C++$写。

串的模式匹配

所谓模式匹配，就是在主串中查找与模式串（待搜索的字符串）完全相同的子串，并返回其首次出现的位置。

首先介绍一种最简单的做法——暴力匹配

大力出奇迹的暴力搜索

int ViolenceSearch(const string& text, const string& pattern) 
{
	int n = text.size();	// 主串长度
	int m = pattern.size();	// 模式串长度

	for (int i = 0; i <= n - m; ++i) 
	{
		int j = 0;
		while (j < m && text[i + j] == pattern[j]) 
		{
			++j;
		}
		if (j == m) 
		{
			return i; // 找到匹配，返回起始位置
		}
	}
	return -1; // 未找到匹配，返回-1
}

不用我说，大家也能看出来这个算法用了双层循环，时间复杂度达到了$O(mn)$。也就是说，模式串或主串但凡长一点，那算法的执行时间将会特别长。而且能看出来，如果一次匹配失败了，那么模式串就会右滑一位，然后重新比较。这个过程中，指针$i$发生了回溯。

那么怎么解决时间的问题呢？我们可以这样想：

分析模式串本身的结构，如果已经匹配成功的序列中有后缀正好是模式串的前缀，那么就可以将模式串右滑到与这些字符对齐的位置，而无需回溯指针$i$。而这，就是$\mathrm{KMP}$模式匹配的核心思想。

あれ？你说你没看懂？大丈夫ですよ，继续往下看吧。

$\mathrm{KMP}$模式匹配算法

概念

  • 前缀：指除了最后一个字符之外，字符串的所有头部子串，即从第一个字符开始的，不走到最后一个字符的子串。

  • 后缀：指除了第一个字符外，字符串的所有尾部子串，即从除了第一个字符之外的所有字符开始，走到最后一个字符的子串。

  • 部分匹配值：指字符串中前缀和后缀的最长相等前后缀长度，即一个字符串的所有前缀和后缀之中，能找到的最长的相等的串的长度。

例如模式串’$ababa$’，我们分析他的每一个子串：

  • ‘$a$’的前缀和后缀都是空串，最长相等前后缀长度是$0$。

  • ‘$ab$’的前缀为${a}$，后缀为${b}$。${a} \cap {b} = \varnothing$，最长相等前后缀长度是$0$。

  • ‘$aba$’的前缀为${a, ab}$，后缀为${a, ba}$，二者取交集结果为${a}$，最长相等前后缀长度是$1$。

  • ‘$abab$’的前缀为${a, ab, aba}$，后缀为${b, ab, bab}$，二者取交集结果为${ab}$，最长相等前后缀长度为$2$。

  • ‘$ababa$’的前缀为${a, ab, aba, abab}$，后缀为${a, ba, aba, baba}$，二者取交集结果为${a, aba}$，最长相等前后缀长度为$3$。

因此，模式串’$ababa$’的部分匹配值为$00123$。

这个时候有的同学就要问了：“啊你说了这一大顿，还是没说出来部分匹配值这玩意儿和$KMP$有什么关系啊。”

光看一个模式串你怎么知道它在$\mathrm{KMP}$里怎么用？还是得把模式串和主串放到一起去看才能看出来。

$\mathrm{KMP}$算法原理

例：假设我们有主串’$ababcabcacbab$’，有模式串’$abcac$’，现在要我们在主串中找出模式串的位置。

这个时候有眼尖的道友们就发现了，哎，那个那个，$abcac$在主串的从左往右数第……第第……第六个位置开始！

对，没错，从主串的第六个位置开始往后查$5$个字符，查的字符拉成串，正好是模式串$abcac$。

但是，可但是但可是，我们能这么快得出结果得益于我们人类有优越于世界上最先进的摄像机的眼睛和在信息处理上超越绝大多数计算机的大脑，因此我们才能从这个主串里快速找到模式串。而这些东西，计算机没有，所以它们只能按照程序算法一步一步去找。

那么这个时候又有同学要问了，啊既然人脑这么好用我们还设计$KMP$干什么呢？

很好，那么大家请看下面这道题：

（深吸一口气）

主串$=$

$$ lkdshfjashfuoapbgishjfuioahrgiuasdbfkjsdbfjkahfaweioughiusgkjashfdoiwehjiuahfjsdbfkjsadlfljkhgkahgiurhgkrbhkjdbfkjshgipusahfuaibhgjkashfkugwrehifuhergiuasbkjfdgnajkfsbhgkahfiorujoirphgifyygieraghtghjaknvajfrouihgkushfgahfgnaflkgnkdjfghiuahjksdbfakjrgojflkjdgakdfhghsgfklhaflskgnvlknjkdslfthiosjtasdiouhkncjblsfdjnmalnekjnmdfsljfnjkasdhgflsjknrjvfnklldsihjfukrkglkfansjkfhuislherfgjrgfnlsdkjgnkfsdrrgdsnjdjfkdjstjhuhfdsyagrdnsmnfbahdjbfvagdsjhfadsntrbadfknjsncakshgdfsdjh $$

模式串$=$

$$ hgkahfioruj $$

好了，道友们去找吧，模式串出现在主串的哪个位置？

呀不行，看得眼睛都疼，找不到。

是吧，现实的生产生活领域我们遇到的大多数问题都是上面这种规模，总不能指望我们一个字符一个字符地挑吧？因此，我们需要$KMP$模式匹配算法。

回到题目

根据前文我们使用的最长相等前后缀长度，我们可以得知模式串$abcac$的部分匹配值是$00010$，将部分匹配值组织成数组的形式，就构成了部分匹配值表($\mathrm{Partial}$ $\mathrm{Match}$ $\mathrm{Table}$，$\mathrm{PM}$表)：

编号 $1$ $2$ $3$ $4$ $5$
模式串 $a$ $b$ $c$ $a$ $c$
$\mathrm{PM}$值 $0$ $0$ $0$ $1$ $0$

下面我们用$\mathrm{PM}$表进行字符串匹配：

第一趟匹配：

编号 $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $12$ $13$
主串 $a$ $b$ $a$ $b$ $c$ $a$ $b$ $c$ $a$ $c$ $b$ $a$ $b$
模式串 $a$ $b$ $c$                    

在第三位发生失配（$c \neq a$），此前已匹配了两个字符’$ab$’，查表可知，最后一个匹配字符$b$对应的部分匹配值是$0$。我们按照下面的公式计算模式串需要右滑的位数：

$$ \text{右滑位数} = \text{已匹配字符数} - \text{最后一个匹配字符的部分匹配值} $$

由于$2 - 0 = 2$，所以将模式串向右滑动$2$位，进行第二趟匹配。

第二趟匹配：

编号 $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $12$ $13$
主串 $a$ $b$ $a$ $b$ $c$ $a$ $b$ $c$ $a$ $c$ $b$ $a$ $b$
模式串     $a$ $b$ $c$ $a$ $c$            

在第五位发生失配（$c \neq b$），此前已匹配了四个字符’$abca$’，查表可知，最后一个匹配字符$a$对应的部分匹配值为$1$，$4 - 1 = 3$，将模式串向右移动$3$位，进行第三趟匹配。

第三趟匹配：

编号 $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $10$ $11$ $12$ $13$
主串 $a$ $b$ $a$ $b$ $c$ $a$ $b$ $c$ $a$ $c$ $b$ $a$ $b$
模式串           $a$ $b$ $c$ $a$ $c$      

模式串全部字符匹配成功。

综上所述，部分匹配值的核心价值在于求模式串在发生失配后最佳的向右移动距离，整个过程中，主串的指针始终没有回溯，这使得$\mathrm{KMP}$算法的时间复杂度稳定在$O(n + m)$。

那么为什么从始至终主串的指针没有回溯呢？因为$\mathrm{PM}$表保存的是模式串的从最开始到每个字符的子串中具有的最长前后缀长度，就可以理解为模式串从前往后数和从后往前数这么多位的字符是相同的。

如果某趟匹配发生失败：已匹配序列中不存在相等的前后缀（$\mathrm{PM}$值为$0$），此时滑动位数最大，直接将模式串首字符对齐到主串的失配位置；若存在相等的前后缀（$\mathrm{PM}$值不为$0$），则将模式串右滑到与主串中该相等后缀对齐的位置，从而跳过已知的相等部分。

$\mathrm{next}$数组

算法原理讲明白了，我们该如何用程序实现这一过程呢？

$\mathrm{KMP}$算法的核心特点是：每趟匹配失配时，主串指针$i$不回溯，仅调整模式串指针$j$。

为此，我们定义一个$next$数组，$next[j]$的含义是：当模式串第$j$个字符失配时，下一轮应从模式串的第$next[j]$的位置继续与主串当前字符比较。

手算$\mathrm{next}$数组

考试里如果让我们手动求$next$数组，其实一句话就能概括：$next[j]$就是第$j$个字符之前那段子串的最长相等前后缀长度再加$1$。

定义

对模式串$T$（下标从$1$开始，长度为$m$）：

  • $next[1] = 0$；
  • 当$j > 1$时，$next[j]=$子串$T[1..j-1]$的最长相等前后缀长度$+\,1$。

注意：求的是第$j$个字符前面的子串$T[1..j-1]$，不含第$j$个字符本身。

手算步骤

  1. 写下模式串，标好下标$1 \sim m$；
  2. 第一个位置固定填$0$；
  3. 从$j = 2$开始，每次把第$j$个字符”盖住”，只看左边剩下的子串$T[1..j-1]$，求它的最长相等前后缀长度$L$，填$L + 1$即可。

以$\mathrm{abcac}$为例

先摆好模式和下标：

编号 $1$ $2$ $3$ $4$ $5$
模式串 $a$ $b$ $c$ $a$ $c$

再逐位计算：

$j$ $T[1..j-1]$ 最长相等前后缀 长度$L$ $next[j]=L+1$
$1$ （空串） 无 —— $0$
$2$ $a$ 无 $0$ $1$
$3$ $\mathrm{ab}$ 无 $0$ $1$
$4$ $\mathrm{abc}$ 无 $0$ $1$
$5$ $\mathrm{abca}$ $a$ $1$ $2$

于是$next$数组为：

编号 $1$ $2$ $3$ $4$ $5$
$next[j]$ $0$ $1$ $1$ $1$ $2$

与$\mathrm{PM}$表的关系

对比前面的部分匹配值表就会发现，$next$数组不过是$\mathrm{PM}$表”整体右移一位、每位加一、首位补零“的结果：

$$ next[1] = 0, \qquad next[j] = PM[j-1] + 1 \quad (j \ge 2) $$
编号 $1$ $2$ $3$ $4$ $5$
$\mathrm{PM}$值 $0$ $0$ $0$ $1$ $0$
$next[j]$ $0$ $1$ $1$ $1$ $2$

求$\mathrm{next}$数组的程序

根据上面的分析内容，可以得到求解$next$数组的程序如下

void getNext(string& p, int* next) 
{
	int i = 1, j = 0;
	next[1] = 0;	// 假设next数组下标从1开始。
	while (i < p.length())
	{
		if (j == 0 || p[i] == p[j]) 
		{
			i++;
			j++;
			next[i] = j;		// 若p[i] = p[j]，则next[j + 1] = next[j] + 1
		} 
		else 
		{
			j = next[j];		// 否则令j = next[j]，继续比较
		}
	}
}

$\mathrm{nextval}$数组：$\mathrm{next}$的优化

前面求出的$next$数组，其实还有一处可以偷懒的地方，这就是考研里经常露脸的$nextval$数组。

问题出在哪儿呢？当模式串第$j$个字符失配时，$next$数组让我们把$j$退回到$next[j]$。可万一$p[j]$和$p[next[j]]$恰好是同一个字符，那退回去之后再拿$p[next[j]]$去和主串比较，结果必然又是失配——白白多比了一次。

为了去掉这种无效回退，我们把$next$进一步优化成$nextval$：

  • $nextval[1]=0$；
  • 当$j>1$时，若$p[j]=p[next[j]]$，则$nextval[j]=nextval[next[j]]$（继续往前跳，直到跳到一个不同的字符或$0$）；否则$nextval[j]=next[j]$（和$next$完全一样）。

一句话，$nextval$就是在$next$的基础上，把那些跳过去还是会失配的位置一次性跳到底。

以$\mathrm{abcac}$为例。先有$next=[0,1,1,1,2]$，再逐位求$nextval$：

$j$ $p[j]$ $next[j]$ $p[next[j]]$ 是否相等 $nextval[j]$
$1$ $a$ —— —— —— $0$
$2$ $b$ $1$ $a$ 否 $1$
$3$ $c$ $1$ $a$ 否 $1$
$4$ $a$ $1$ $a$ 是 $nextval[1]=0$
$5$ $c$ $2$ $b$ 否 $2$

于是$nextval=[0,1,1,0,2]$。把它和$next$放一起对比：

编号 $1$ $2$ $3$ $4$ $5$
模式串 $a$ $b$ $c$ $a$ $c$
$next$ $0$ $1$ $1$ $1$ $2$
$nextval$ $0$ $1$ $1$ $0$ $2$

可以看到，只有第$4$位（字符$a$）变了：用$next$会退回到开头的$a$，而这个$a$注定又要和刚才的失配字符比一次、再失配一次；用$nextval$则直接退到$0$，把这次没用的比较省掉。

一个例子：$\mathrm{aaaab}$与$\mathrm{aaabaaaab}$

abcac那点优化还不够震撼，我们换一个”重灾区”来看看$next$数组到底会多比多少次。

模式串$aaaab$，目标串$aaabaaaab$。

先求两个数组：

编号 $1$ $2$ $3$ $4$ $5$
模式串 $a$ $a$ $a$ $a$ $b$
$next$ $0$ $1$ $2$ $3$ $4$
$nextval$ $0$ $0$ $0$ $0$ $4$

先看用$next$数组匹配的过程：开局三个字符一路顺风，到第$4$位出事——$s[4]=b$和$p[4]=a$失配：

编号 $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$
目标串 $a$ $a$ $a$ $b$ $a$ $a$ $a$ $a$ $b$
模式串 $a$ $a$ $a$ $a$ $b$        

按照$next$数组，$j$退回$next[4]=3$，于是拿$s[4]=b$去和$p[3]=a$比——失配；再退回$next[3]=2$，比$p[2]=a$——又失配；再退回$next[2]=1$，比$p[1]=a$——还是失配；一直退到$next[1]=0$，才把$i$和$j$同时右移。

问题一目了然：因为$p[4]=p[3]=p[2]=p[1]=a$，$next$数组让$j$退回的每一个位置，字符都和刚刚失配的那个$a$一模一样。既然$s[4]=b$已经和$a$比失败了一次，那再拿一个一模一样的$a$去比，结果必然是继续失败。这就是$p[j]=p[next[j]]$时$next$数组凭空多出来的无用比较——每退回一步，就多做一次注定失败的比较；本例中$j$从$4$一路退到$0$，一共多比了$3$次。

换成$nextval=[0,0,0,0,4]$再看：同样在第$4$位失配，但此时$j$退回$nextval[4]=0$，跳过的正是一连串注定失败的$a$，直接让$i$右移、$j$归$1$继续往下走。三次无用比较，被一次省掉；之后一路顺利，最终模式串出现在目标串的第$5$个位置。

求$\mathrm{nextval}$数组的程序

$nextval$的代码和$next$几乎一样，只是在每次求出$next[i]=j$之后多判断一步：如果$p[i]=p[j]$，说明跳到$j$还是免不了失配，那就让它继承$nextval[j]$；否则仍和$next$一样取$j$。

void getNextval(string& p, int* nextval) 
{
	int i = 1, j = 0;
	nextval[1] = 0;	// 假设nextval数组下标从1开始。
	while (i < p.length())
	{
		if (j == 0 || p[i] == p[j]) 
		{
			i++;
			j++;
			if(p[i] != p[j]) 
			{
				nextval[i] = j;				// 字符不同，与next一样
			} 
			else 
			{
				nextval[i] = nextval[j];	// 字符相同，直接继承
			}
		} 
		else 
		{
			j = nextval[j];					// 注意这里用的也是nextval
		}
	}
}

$\mathrm{KMP}$算法主程序

有了$next$（或者优化后的$nextval$）数组做基础，我们回到$KMP$模式匹配算法。其代码结构与暴力匹配类似，但是在发生失配时，主串指针$i$保持不变，只将模式串指针$j$回退到$next[j]$（若用优化版，则回退到$nextval[j]$）所指的位置，并继续比较；特别的，当模式串第一个字符就失配时，此时$j = 0$，我们就把$i$和$j$同时加$1$。具体实现如下：

int KMP(string& s, string& t, int* next) 
{
	int i = 1, j = 1;
	while (i <= s.length() && j <= t.length())
	{
		if (j == 0 || s[i] == t[j])		// 继续比较后面的字符
		{
			i++;
			j++;
		} 
		else						// 模式串向右滑动
		{
			j = next[j];
		}
	}
	if (j > t.length())			// 匹配成功
	{
		return i - t.length();
	}
	else						// 匹配失败
	{
		return 0;
	}
}

结语

尽管暴力匹配的最坏时间复杂度为$O(mn)$，而$KMP$模式匹配算法最坏情况下是$O(m + n)$，但因为在一般情况下，暴力匹配的时间复杂度还是$O(m + n)$，且$KMP$算法只有在主串与模式串存在大量部分匹配情况时才显著优于暴力匹配。所以至今暴力匹配仍在很多情形下都有应用。