数据结构笔记

第一章 绪论

1.1 数据结构的基本概念

数据间的分类和关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
数据（Data）  
│  
├── 数据对象（Data Object）  
│   └── 数据元素（Data Element）  
│       └── 数据项
├── 数据类型（Data Type）  
│   ├── 基本类型（Primitive）  
│   ├── 复合类型（Composite）  
│   └── 抽象类型（ADT）  
│  
└── 数据结构（Data Structure）  
    ├── 逻辑结构（如线性、树形）  
    └── 存储结构（如顺序、链式）  

数据元素是数据对象中的一个单位，例如链表节点是链表的一个元素。
基本数据类型也就是原子类型，包括int、float、char等不可分类型。
复合数据类型也就是结构类型，包括枚举、数组、结构体等，可以拆分为基本类型。
抽象数据类型（ADT）是用户定义的逻辑结构，包含数据和操作的封装，如列表、树、图等。

抽象数据类型可以定义一个完整的数据结构，而基本数据类型和复合数据类型却不能，这是因为基本数据类型和复合数据类型没有定义数据元素之间的逻辑关系（如线性、树形、图状结构结构等），也没有定义数据的操作方式（插入、删除、查找）和存储结构的实现细节（如顺序存储或者链式存储）

2、数据结构包含三个要素：逻辑结构、存储结构和数据的运算。算法的设计或定义取决于逻辑结构，而算法的实现取决于存储结构。

1
2
3
4
5
6
7
8
9
10
11
逻辑结构与存储结构无关，分为线性结构和非线性结构。
线性结构（栈、队列、数据、串、一般线性表等）
非线性结构（集合、树、图等）
集合中的元素无关。
线性结构中的元素存在一对一的关系。
树形结构中的元素存在一对多的关系。
图状结构中的元素存在多对多的关系。

存储结构也称物理结构，包括数据元素的表示和关系的表示。主要包括顺序存储、链式存储、索引存储、哈希散列存储。

数据的运算包括定义和实现，定义与逻辑结构相关，实现与存储结构相关。

1.2 算法和算法评价

1、算法的五个特性：有穷性、确定性、可行性、输入和输出。

2、优秀算法的四个要求：正确性、可读性、健壮性、高效率和低存储量要求。

3、算法效率的度量是通过时间复杂度和空间复杂度来描述的。

1
2
3
时间复杂度指算法中基本运算的执行次数的数量级，有最坏时间复杂度、平均时间复杂度和最好时间复杂度。

空间复杂度指除去输入和程序之外的额外空间，也就是辅助空间的大小。如果算法所需的辅助空间为常量，则算法的空间复杂度为O(1)。如果算法的所需的辅助空间和算法的问题规模相关，则空间复杂度为跟n相关的函数。

常见的时间复杂度排序如下
$$
O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)\<O(n^3)<O(2^n)<O(n!)<O(n^n)
$$

第二章 线性表

2.1 线性表的定义和基本操作

1、线性表是具有相同数据类型的n个数据元素的有限序列。

1
2
3
4
需要注意线性表是有限的，且线性表中的每个元素都是相同的类型。
线性表中除了表头和表尾元素，其余元素都有前驱和后继。
线性表中的逻辑关系：⚪ -> ⚪ -> ⚪
只有相邻的元素才有关系

2、线性表是一种逻辑结构，顺序表和链表才是其存储结构。

2.2 线性表的顺序表示

1、顺序表是线性表的顺序存储。

1
2
3
在读题时注意区分线性表和顺序表。
顺序表是线性表的顺序存储结构的实现。
线性表是逻辑结构，存储结构可以是顺序表或者链表。

2、顺序表的特点是元素的逻辑顺序和存储的物理顺序相同。

1
注意在线性表中位序从1开始，但是在数组中存储中元素的下标是从0开始的。

3、顺序表的存储空间可以通过静态分配或者动态分配。

1
2
静态分配是固定大小，如果溢出就会导致程序错误终止。
动态分配则是通过malloc动态分配连续的存储空间，如果刚开始分配的空间不足，可以再次分配，但是需要找到更大的连续存储空间，如果找不到就会扩充失败。

4、顺序表存储的优点是可以随机访问，且存储密度高，但是在进行需要对元素进行移动的操作时速度较慢，且需要连续的存储空间，存储模式不够灵活。

5、插入操作，在插入时需要将后续元素后移。

1
2
3
4
在第i个位置插入时，需要将后续的n-i+1个元素后移。
在后移时应当从末尾开始移动，提高效率。
由于在n个数中有n+1个间隔，因此插入每个间隔中的概率是相同的1/(n+1)
插入算法的平均插入次数为n/2，时间复杂度为O(n)

6、删除操作，在删除时需要将后续元素前移。

1
2
3
4
在第i个位置插入时，需要将后续的n-i个元素前移。
在前移时应当从起始处开始移动，提高效率。
每个元素被删除的概率是1/n。
删除算法的平均删除次数为(n-1)/2，时间复杂度为O(n)

7、按值查找，遍历

1
按值查找算法的平均查找次数为(n+1)/2，时间复杂度为O(n)

按序号查找的时间复杂度为O(1)，因为顺序表是可以随机存取的。

2.3 线性表的链式表示

1、链表是线性表的链式存储形式。

1
2
3
4
链表不要求逻辑结构中的相邻元素在物理存储结构上也相邻。
尽管元素外部不一定相邻，但是元素内部的数据项是连续存储的。
由于在物理结构上不相邻，链表中的每个元素中除了数据域还需要指针域指向相邻节点。
由于指针域的存在，链表的存储密度是要低于顺序表的。

2、通常用头结点来标识一个链表，头结点的数据域可以设置数据或者不设置数据。

1
头结点的存在便利了对链表第一个元素的特殊判断，简化了算法。

3、求表长操作，遍历一遍，时间复杂度为O(n)。

4、按序号查找结点，遍历一遍，时间复杂度为O(n)。

1
如果是顺序表的话，时间复杂度为O(1)。

5、按值查找结点，遍历一遍，时间复杂度为O(n)。

6、插入结点，时间复杂度为O(n)。

1
2
在插入结点时为了防止断链，通常需要先将要插入的结点与后继结点连接之后，再将前驱结点与后继结点断开连接。
尽管插入结点操作本身是O(1)操作，但是查找结点却是O(n)操作，因此插入结点的时间复杂度为O(n)

7、删除结点，时间复杂度为O(n)。

1
与插入结点类似，体现时间复杂度的主要操作是查找结点。

8、建立链表，建立链表可以使用头插法或者尾插法，时间复杂度为O(n)

1
2
使用头插法时，每次插入的元素都作为第一个元素，因此读入元素的顺序和生成的链表中的元素顺序是相反的，也就是逆序，可以用来实现链表的逆置。
使用尾插法时，需要尾指针的辅助，输入元素的顺序跟生成的链表中的元素顺序相同。

9、双链表的插入结点操作，时间复杂度为O(n)

1
与单链表不同的是，双链表的插入需要对四个指针域进行修改，同样也需要保证在插入的过程中不断链。

10、双链表的删除结点操作，时间复杂度为O(n)。

11、循环链表，分为循环单链表和循环双链表。

1
2
3
4
循环链表与非循环链表的区别在于循环链表中的最后一个结点的指针会指向链表的头结点而不是NULL。
如果在没有头结点的链表中则指向第一个结点。
对于存在尾指针的循环单链表，在表头或者表尾插入结点的时间复杂度都是O(1)，而对于只有头指针的单链表在表尾插入结点则是O(n)。
循环双链表与循环单链表类似，只是需要维护的指针域比较多。

12、静态链表是通过数组模拟链表的存储结构实现。在结点中有数据域和指针域，但是此处的指针是结点在数组中的数组下标（相对地址），也称游标。

1
2
静态链表无法实现随机存取，但是需要连续的存储空间，一般以指针域为-1作为表尾结束标志。
静态链表一般用于没有实现指针功能的高级语言中，作为链表的替代品。

13、题目小知识

1
2
3
4
链式存储结点内的元素存储地址是连续的（注意辨别是结点内还是相邻结点间）。
如果是用单链表来表示队列，应该使用带有尾指针的循环链表，便于实现先进先出（从表头删除，表尾插入）
给定有n个元素的一维数组用于建立有序单链表时，最低的时间复杂度为O(nlogn)。
可以先通过排序得到有序，再建立链表，即nlogn + n，得到nlogn。

第三章 栈、队列和数组

3.1 栈

1、栈是只允许在一端进行插入或删除的线性表。

1
2
可以注意到栈是线性表，栈的主要结构有栈顶和栈底，操作时只能从栈顶入栈和出栈，是后进先出的模式(LIFO)。
LIFO: last in first out

2、栈的基本操作有初始化栈、栈空、栈满、出栈、入栈、销毁栈、读栈顶元素等。

1
2
3
当n个不同元素入栈时，出栈元素不同排列的个数符合卡特兰数。
会出现这种情况的原因是出栈时不必在栈满时，只需在栈不为空时即可出栈，因此会出现多种可能的排列。
由相同的入栈序列也不一定能得到一样的出栈序列。

$$
卡特兰数 = \frac{1}{n+1}C_{2n}^n
$$

3、栈的顺序实现称为顺序栈。顺序栈的存储结构是连续的，包含栈中元素和指向栈顶的指针。

1
2
3
4
指向栈顶的指针可能指向栈顶元素，也可能指向栈顶元素的下一个元素，都是常见的写法，做题时应当注意，在数据结构的所有时刻，都应当维持该数据结构的规则，对数据结构进行维护。
由于指向栈顶指针的写法不同，在判断栈空，栈满，出栈和入栈时的写法也有所不同，需要仔细体会。
栈空时出栈称为栈的下溢。
栈满时入栈称为栈的上溢。

4、入栈时栈顶指针加一，出栈时栈顶指针减一，出栈时需要判断栈是否为空，入栈时需要判断栈是否为满。

5、共享栈，利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间。

1
2
3
共享栈就是两个栈共用一片空间，栈底分别在左右两侧，栈顶向中间增长。
优点是更有效地利用了存储空间，因为顺序栈是提前固定分配的空间，如果栈不满的话就会浪费一些空间。
在栈顶指针的初始状态不同时，共享栈判定栈满的条件不同。

6、栈的链式实现称为链栈。

1
2
3
链栈的优点是不存在栈满上溢的情况。（除非内存满了）
通常使用单链表实现链栈，所有操作都是在链表表头进行，符合后进先出的规则。
对于带头结点和不带头结点的链栈，具体的操作实现有所不同，需要具体情况具体分析，但是不管怎样肯定是符合栈的规则的。

7、题目小知识

1
在遇到计算出栈序列和进栈序列时，一般不用将所有的情况都列举出来，只需要对选项进行验证即可。

3.2 队列

1、队列是操作受限的线性表，只允许在表的一端进行插入，另一端进行删除。

1
2
3
4
注意到队列也是线性表，队列的主要结构为队内元素，队首（队头）指针和队尾指针。
队列符合先进先出的规则FIFO。
队列一般是尾进头出。
FIFO: first in first out

2、队列的基本操作有初始化队列、队列空、入队、出队、读队首元素等。

1
栈和队列是操作受限的线性表，无法对栈或队列中的某个数据进行随机读取。

3、队列的顺序存储称为顺序队列。

1
2
3
顺序实现是分配的一块连续的存储单元，队首指针front指向队首元素，队尾指针rear指向队尾元素的下一个位置。
对队首指针和队尾指针的定义可能根据题目有所不同，需要根据题目具体分析。
有些题目中会让队尾指针rear指向队尾元素。

4、在顺序队列中，入队时队尾指针rear加一，出队时队首指针front加一。

1
2
当front == rear时，判定队列为空。
由于出队时队首指针会加一，但是没有操作使得队首指针返回队列的起点。队列的空间是固定不变的，如果一直入队使得队尾指针无法再增加，此时是否能认为队列已经满了呢，显然是不能的，因为在队首指针之前可能还有未被利用的空间，这就是队列的假溢出。（上溢）

5、为了解决顺序队列的假溢出，可以使用循环队列。

1
2
3
4
5
6
7
8
9
10
循环队列也是顺序存储的。
当队首指针front = maxsize - 1时，将front置为0，也就是回到队列的起点。
循环队列与顺序队列的基本操作相同，但是具体细节上有所不同。
入队时，rear = (rear+1)%maxsize
出队时，front = (front+1)%maxsize
队列长度，length = (rear+maxsize-front)%maxsize
判断队空，rear == front
但是由于循环的存在，使用如果不对循环队列作处理的话，队空和队满的判断条件都是rear == front，这样就会造成混淆。
因此一般会将最后一个队列单元置空，这样当(rear+1)%maxsize == front时，就能判断队满了。
或者增设一个记载队列长度的变量，还可以通过增加标志变量的方式辨别队空或者队满，需要根据题目具体分析。

6、队列的链式存储称为链式队列。

1
2
3
链式队列实际上是一个同时有队首指针和队尾指针的单链表。
存在尾指针是因为队列遵循尾进头出的规则，设置尾指针方便了操作。
相比于顺序队列或者循环队列，链式队列通常不会出现存储分配不合理和溢出的问题。

7、双端队列是指允许两端都可以进行插入和删除的线性表。

1
2
3
4
5
6
双端对列包含几个种类。
输出受限的双端队列，两端都能插入，但是只有一端能删除。
输入受限的双端队列，两端都能删除，但是只有一端能插入。
输入受限的双端队列相当于两个栈底相接的栈。
输出和输入都不受限的双端队列，也就是普通的双端队列。
双端队列常考的是输入序列和输出序列的辨析，关于这种题目一般代入选项进行验证即可，不需要全部排列。

8、题目小知识

1
2
3
4
链式存储尽管在存储空间上更加自由，通常不会溢出，但是还是受内存大小的限制。
链式队列无法使用队首指针和队尾指针计算队列的长度，因为其长度是不固定的。
对链式队列进行删除操作时可能需要对头尾指针都修改，尽管在一般情况下只需要对头指针进行修改，但是如果删除之后队列为空的话，则需要将头尾指针都指向NULL。
头指针、尾指针和头结点是不同的概念，有头指针时不一定有头结点。

3.3 栈和队列的应用

1、栈可以用于括号的匹配。

1
设置一个空栈，将序列进行遍历，若为左括号，则入栈，若为右括号，则查看栈顶是否为匹配的左括号，如果是则出栈，否则终止程序，匹配失败。若遍历完成之后，栈内还有左括号，匹配失败。

2、栈可以用于表达式的求值。

1
2
3
包括将中缀表达式转化为后缀表达式，以及对后缀表达式进行求值。
将中缀表达式转为后缀表达式时通常将其转为二叉树再转为后缀表达式。
对后缀表达式求值时则往往是根据题目中给出的求值过程继续分析。

3、栈可以用于递归。

1
程序调用时变量存储在栈中，出口和参数也是通过栈结构进行存储。

4、队列可以用于层次遍历。

1
例如树的层次遍历或者bfs，这种对广度进行求解的情况。

5、队列还能解决主机与外设运行速度不匹配和解决多用户引起的资源竞争问题。

1
2
主机与外设不匹配时需要设置数据缓冲区，数据缓冲区是先进先出的，符合队列的规则。
多用户引起的资源竞争问题也是先到先得，符合队列的规则。

6、题目小知识

1
对中缀表达式进行转换时只能得到唯一的后缀表达式

3.4 数组和特殊矩阵

1、数组是有限个相同类型元素组成的序列。

1
2
可以注意到跟线性表的定义类似。
除了创建和销毁数组之外，只能对数组元素进行存取和修改，无法对其进行删除或者增加。

2、数组的存储结构是一段连续的存储空间。

3、二维数组存在两种存储形式，一种是行优先存储，一种是列优先存储。

1
2
行优先存储就是先存储第一行再存储第二行，横向优先。
列优先存储就是先存储第一列再存储第二列，纵向优先。

4、对于特殊矩阵，可以对其进行压缩存储。

1
压缩存储并不是对不存在的元素进行压缩，而是对相同的元素进行压缩，对零元素不分配空间。

5、对于对称矩阵

1
2
3
4
5
6
7
对于矩阵a，a(i,j) = a(j,i)，这就是对称矩阵。
对称矩阵一般可以只存储上三角或者下三角以及对角线处的元素即可，也就是说对称矩阵可以缩减为上三角矩阵或者下三角矩阵。
用于存储n行对称矩阵的一维数组，一般长度为n(n+1)/2
对于矩阵中的元素下标和数组中的数组下标中的对应关系，一般为
k = i(i-1)/2 + j - 1（下三角矩阵）
在遇到具体题目时一般是通过等差数列直接推导，公式太难记了。
二维数组A[n][n]一般为[0...n-1][0...n-1]，和A[1...n][1...n]是不同的。

6、对于三角矩阵

1
三角矩阵分为上三角矩阵和下三角矩阵，存储的方式跟对称矩阵差不多。

7、对于三对角矩阵

1
2
3
对角矩阵也称带状矩阵，三对角矩阵的定义是，对于矩阵中的任意一个元素a(i,j)，当|i-j|>1时，a(i,j) = 0，也就是说只有对角线附近的元素不为0。
在三对角矩阵中，第一行和最后一行为两个元素，其余行为三个元素，根据这个特点就能计算出矩阵下标和压缩存储的数组下标的对应关系。
根据推测，应该只有五对角矩阵，没有四对角矩阵。

8、对于稀疏矩阵

1
2
3
4
5
6
矩阵中非零元素相对于整个矩阵的元素来说非常少，通常达到了一百倍的差距，将这种矩阵称为稀疏矩阵。
注意不是没有元素，而是元素大部分为0。
可以对稀疏矩阵进行压缩存储，压缩为三元组表或者十字链表。
对于三元组表，三元分为是行号、列号和值。
在压缩为三元组表时，还需要存储稀疏矩阵的行数、列数和非零元素的个数。
压缩之后的稀疏矩阵，由于存储位置和序号无关，无法进行随机存取，只能根据行号和列号进行查找。

第四章 串

4.1 串的定义和实现

1、串是由零个或多个字符组成的有限序列。

1
串中任意多个连续字符组成的子序列称为该串的子串，包含子串的串称为主串。串的逻辑结构和线性表类似，但是串的数据对象只能是字符集。

2、串的赋值、串的比较、求串的长度、串的拼接、求子串五种操作构成串类型的最小操作子集，其他操作都可以通过这五种操作得到。

1
除了串清除和串销毁

3、串的定长顺序存储表示，用一组地址连续的存储单元来存储串值的字符序列。

4、串的堆分配存储表示，仍然使用一组地址连续的存储单元存储，但是不是在程序执行前固定分配的，而是在程序执行的过程中动态分配的。

5、串的块链存储，类似线性表的链式存储结构，每个结点可以存储一个或多个字符，结点称为块。

4.2 串的模式匹配算法

1、模式匹配是指在主串中找到与模式串相同的子串，并返回其所在的位置。

2、暴力匹配算法：主串长度为n，模式串长度为m。

1
2
3
4
从主串的第一个字符开始，对模式串进行匹配。
每次匹配流程如下：主串指针和模式串指针同步增加，如果失配，则退出匹配流程。
退出匹配流程之后，主串指针指向到主串的下一个字符，模式串指针指向模式串的第一个字符。
直到主串剩余的字符串长度小于模式串的长度或者匹配成功。

在暴力匹配算法中，最多需要进行n-m+1次匹配，每次匹配最多需要进行m次比较，最坏时间复杂度为O(nm)。

3、串的模式匹配算法——KMP算法

在暴力算法中，每次失配都要从主串的下一个字符和模式串的第一个字符开始。但是如果已经匹配相等的前缀序列中有某个后缀正好是模式串的前缀，则可将模式串向右滑动到与这些相等字符对齐的位置。注意在KMP算法中，主串指针一直递增，向右滑动的是模式串的指针。

1
2
3
例如abcabcacab和abcac比较，
可以发现第一次匹配时，在进行第五次比较，也就是abcab和abcac比较时失败，如果按照暴力算法，此时主串指针回退到b，模式串指针回退到第一位，然后对bcabcacab和abcac进行比较。
然而如果按照KMP算法，在已经匹配相等的前缀序列abca中，后缀a刚好跟abca的前缀a相等，那么首尾重合，可以将abca右移三位，将主串abcacab和abcac进行比较，此处跳过了bc两位，主串指针没有回退，模式串指针指向第二位。

模式串向右滑动的位数只和模式串本身相关，与主串无关。

4、KMP算法的原理

从上文可以看到，在KMP算法中，最重要的是在已经匹配相等的前缀序列中有某个后缀正好是模式串的前缀。而已经匹配相等的前缀序列其实就是模式串的前缀序列。所以其实本质上是指在已经匹配的模式串部分是否存在前后缀相等的情况。

1
2
3
4
5
6
7
对于模式串ababa
假设已经匹配的前缀序列为a，a的前缀和后缀都为空，最长相等前后缀长度为0。
假设已经匹配的前缀序列为ab，ab的前缀为a，后缀为b，最长相等前后缀长度为0。
假设已经匹配的前缀序列为aba，aba的前缀为a、ab，后缀为a、ba，最长相等前后缀长度为1。
以此类推，abab的最长相等前后缀长度为2，ababa的为3。
所以模式串ababa的部分匹配值为00123。
根据部分匹配值列表可以得到部分匹配表，也就是PM表。
1
2
3
4
5
此处再以主串abcabcacab和模式串abcac为例。
根据计算可以得出，abcac的部分匹配值为00010。
当abcab和abcac匹配时，可以看到在第五位，也就是b和c匹配时失败，此时如果按照暴力算法，应该回退到第二位的b。
但是按照KMP算法，利用刚才计算出来的部分匹配值，在已经匹配的abca中，部分匹配为1，存在相同的前缀和后缀，此时将模式指针指向第四位的a，相比于匹配的起始指针右滑了三位，除了本身需要滑动的一位之外，还跳过了不需要匹配的两位。
右滑位数 = 已经匹配的串长 - 串对应的部分匹配值

5、next数组手算方法

在KMP算法中，主串指针只会一直递增，而当每次匹配失败时，模式串会不断向右滑动。

由于实际算法中，模式串是固定的，不会一直滑动，所以表现出来的形式是指向模式串的指针变化。也就是说模式串向右滑动跟模式串的指针变化是等价的。

为此可以定义一个next数组，next[j]的含义是当模式串的第j个字符匹配失败时，模式串跳转到next[j]的位置继续匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
以abcac为例。

假设第一个字符a处匹配失败，也就是说j=1，此时其实匹配已经结束了，但是为了符合next数组的定义，next[1] = 0。
可以这样理解，在第一个字符就匹配失败，按照算法来说，退出匹配之后，主串指针会加一，让下一个主串字符跟模式串进行匹配。而在下一个主串字符跟模式串匹配时，上一个字符其实是跟模式串的第零位在进行匹配。
如果调换一下顺序，在第一个字符匹配失败后，模式串跳转到第零个字符，也就是模式串向右滑动了一位，然后结束匹配。结束匹配之后，主串的指针递增。这样就完美符合了next数组的定义。

假设第二个字符b处匹配失败，即j=2。此时模式串应该跳转到next[2]处进行匹配，next[2] = 1。此处是正常逻辑，如果失配，则从模式串的第一位开始匹配，模式串向右滑动一位。
此处跟PM值是对应的，在对第二个字符进行匹配时，已匹配的字符数为1，此时是没有前缀和后缀的，部分匹配值为0。

从第三个字符开始，已匹配的字符串大于等于2，此时可能会出现有效的部分匹配值。
在遇到有效的部分匹配值时，不能直接令next[j] = 1，也就是从头开始匹配模式串，而要从部分匹配的后缀的第一位字符处开始。

假设第三个字符c处匹配失败，则j=3，next[3] = 1，从模式串的第一位开始重新匹配，模式串向右滑动两位。
假设第四个字符a处匹配失败，则j=4，next[4] = 1，从模式串的第一位开始重新匹配，模式串向右滑动三位。
假设第五个字符c处匹配失败，与之前的情况不同，此时已匹配的字符串abca中出现了最长相等前后缀长度为1的情况，abca的部分匹配值为1，那么此时只需从模式串的第四位，也就是a处开始，模式串向右滑动了三位。next[5] = 2。

可以看出next[j] = j - 右滑位数，而从上文中可以得到，右滑位数 = 已匹配的字符数 - 部分匹配值 = (j-1) - PM[j-1]
可以得到next[j] = PM[j-1] + 1
也就是说next表就是部分匹配值的表向右移加一，且next表的第一个值为0。

6、next数组的定义公式
$$
设主串为s_1s_2…s_n，模式串为p_1p_2…p_n。
$$
当主串的第i个字符与模式串的第j个字符失配时，可能存在三种情况。

第一种，j=1，此时主串应该和模式串的第零个字符匹配，next[j]=0。

第二种，j不等于1且已匹配的字符串中不存在最长相等前后缀，那么此时让主串的第i个字符和模式串的第1个字符匹配。
即next[j] = 1。

第三种，j大于等于2且已匹配的字符串中存在最长相等前后缀，假设最长相等前后缀的长度为k-1，即
$$
在已匹配子串p_1p_2…p_{j-1}中，存在k，使得p_1p_2…p_{k-1} = p_{j-k+1}p_{j-k+2}…p_{j-1}
$$
则next[j] = k，右滑位数为j-k。注意此处的最长这个限定词，在已匹配的字符串中可能有多个相等前后缀。

综上所述，next的定义如下
$$
\begin{equation}
next[j] =
\begin{cases}
0, & j = 1 \
max{k|1<k<j且p_1p_2…p_{k-1} = p_{j-k+1}p_{j-k+2}…p_{j-1}}, & 当此集合不为空时 \
1, & 其他情况
\end{cases}
\end{equation}
$$
7、next数组的递推

由于next数组的第一个和第二个元素都是已知的，且next[j] = k也存在递推的性质，因此可以尝试通过之前的next值得到之后的next值。

对于next[j] = k，其相当于
$$
p_1p_2…p_{k-1} = p_{j-k+1}p_{j-k+2}…p_{j-1}
$$
想要求出next[j+1]，易得
$$
如果p_k = p_j，则p_1p_2…p_{k-1}p_{k} = p_{j-k+1}p_{j-k+2}…p_{j-1}p_{j}
$$
那么next[j+1] = k+1。

但是如果不相等呢，那么
$$
在已匹配子串p_1p_2…p_j中，需要找出k’，使得p_1p_2…p_{k’} =p_{j-k’+1}p_{j-k’+2}…p_{j-1}p_{j}
$$
已知k’<k，这是因为k已经是最长相等前后缀了
$$
\begin{array}{l}假设存在k’，在p_1p_2…p_{k-1}中，有\
p_1p_2…p_{k’-1} = p_{k-k’+1}p_{k-k’+2}…p_{k-1}，又\
p_1p_2…p_{k-1} = p_{j-k+1}p_{j-k+2}…p_{j-1}，可得\
p_1p_2…p_{k’-1} = p_{j-k’+1}p_{j-k’+2}…p_{j-1}，则若\
p_{k’} = p_{j}，则\
p_1p_2…p_{k’} =p_{j-k’+1}p_{j-k’+2}…p_{j-1}p_{j}。\
由于p_1p_2…p_{k’-1} = p_{k-k’+1}p_{k-k’+2}…p_{k-1}，\
根据next[j]的定义可得，k’ = next[k]。\
证毕
\end{array}
$$
如果不匹配，则递推使用next[k]，直到k’ = 0
$$
\begin{array}{l}
对于模式串abaabcaba，通过递推得到next数组\
next[1] = 0\
对于next[2]，已知next[1]=0,j=1,k=0，则next[2] = 1。\
对于next[3]，已知next[2]=1,j=2,k=1,p_j=b,p_k=a，则k’ = next[1]=0，根据next数组的定义，next[3] =1 \
对于next[4]，已知next[3] = 1，即j=3,k=1,p_j = p_k = a，则next[4] = next[3] + 1 = 2。\
对于next[5]，已知next[4] = 2,p_j = a,p_k = b，则k’ = next[2] = 1，p_{k’} = p_j = a，则next[5] = next[2] + 1 = 2。\
对于next[6]，已知next[5] = 2,p_j = p_k = b，则next[6] = next[5]+1 = 3。\
对于next[7]，已知next[6] =3,p_j = c,p_k = a，则k’ = next[3] = 1，p_{k’} = a,p_j=c，则k’’ = next[1] = 0，根据next数组的定义，next[7] =1。\
对于next[8]，已知next[7] = 1,p_j=a,p_k=a，则next[8] = next[7] + 1=2。\
对于next[9]，已知next[8] = 2,p_j=b,p_k=b，则next[9] = next[8] + 1 = 3。\
可得abaabcaba的next数组序列为011223123
\end{array}
$$
8、KMP算法的实现

先对模式串进行处理，求出next数组，代码不止下面一种写法，这是按王道的写的，说实话我觉得不太符合我的思考逻辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 参数为模式串和空的next数组
void get_next(SString T,int next[]){
    int j=1,k = 0;
    next[1] = 0
    while(j<T.length){
        if(k == 0 || T.ch[j] == T.ch[k]){
            j++;k++;
            next[j] = k;
        }
        else{
            k = next[k];
        }
    }
}

通过next数组对主串进行匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 参数为主串，模式串，next数组，返回值为主串和模式串匹配的第一个字符的位置
int Index_KMP(SString S,SString T,int next[]){
	int i=1,j=1;
	while(i<=S.length&&j<=T.length){
		if(j==0||S.ch[i] == T.ch[i])
		{
			i++;j++; #匹配成功，继续匹配
		}
		else{
			j = next[j]; #匹配失败，模式串指针跳转到next[j]的位置继续匹配。
		}
	}
	if(j>T.length){
		return i - T.length;
	}
	else{
		return 0;
	}
}

9、KMP算法的优化

之前定义的next数组在某些情况下存在缺陷。
$$
\begin{array}{l}
设主串为s，模式串为p\
在进行模式串和主串的匹配时，若主串和模式串在第i位处失配，证明s_i!=p_i。\
此时模式串的指针指向next[i]处，对s_i和p_{next[i]}进行比较。\
若p_i = p_{next[i]}，那么此时就会造成重复的匹配。\
为了避免出现这种情况，在计算next数组时，\
如果出现p_i = p_{next[i]}的情况，则继续对i进行递推，\
令i’ = next[i]，直到p_i’!=p_{next[i’]}为止，此时next[i’]为最优值。
\end{array}
$$

1
2
3
4
5
6
7
8
对于模式串aaaab和主串aaaba进行分析。
模式串的next数组序列为01234
当主串和模式串进行匹配时，在第四位处失配，即i=4。
此时模式串指针应当指向3，将模式串的第三位a和主串的第四位b进行匹配，再次失配。
此时模式串指针应当指向2，将模式串的第三位a和主串的第四位b进行匹配，再次失配。
以此类推，直到模式串的第一位a和主串的第四位b也失配，才将主串指针加一，与模式串的第一位进行匹配。
可以看到，在上述例子上，进行了多次无效的匹配。
对next数组进行递归，找到最优值可以避免这种情况，即KMP算法的优化。

由于计算next的时候是通过递推得到的，即通过之前的next值得到之后的next值，那么为了实现优化，应当在计算之后的next值时对之前的next进行修改，不可能先得到之后的next值再得到之前的next值。
$$
\begin{array}{l}优化后的算法，对于模式串aaaab\
next[1] = 0
对于next[2]，已知next[1]=0,j=1,k=0\
按照next值的计算方式，此时k=0，则next[2]应该等于1。\
但是p_{next[2]} = p_1 = a，则令next[2] = next[1]=0\
此时符合nextval的条件，next得到最优值。\
对于next[5]，已知next[4]=3,j=4,k=3，p_k = p_j = a，则next[5] = 4\
对于不需要修正的next值，nextval=next。
\end{array}
$$
优化后的算法表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 参数为模式串和空的nextval数组
void get_nextval(SString T,int nextval[]){
    int j=1,k = 0;
    nextval[1] = 0
    while(j<T.length){
        if(k == 0 || T.ch[j] == T.ch[k]){
            j++;k++;
            if(T.ch[j] == T.ch[k]){
                nextval[j] = nextval[k];
            }
            else{
                nextval[j] = k; 
                # 可以理解为k = next[k] + 1，在其中是隐含了next数组的
            }
        }
        else{
            k = next[k];
        }
    }
}

说实话，代码写得太高级了（换作是我就先算整个next数组再算nextval数组，不然逻辑太难厘清了）

10、题目小知识

1
2
3
向右滑动的距离等于j-next[j]

计算时注意细节

第五章 树与二叉树