1. 串的定义和基本操作

1.1 定义

串：即字符串，是由零个或多个字符组成的有限序列。一般记为S = “a1a2a3...an”

其中，S是串名，引号括起来的字符序列是串的值：a1可以是字母、数字或其他字符。

注意：

1. 空格也是字符。
2. 空串不是空格串。
3. 每个字符默认为1B.

* 一些相关术语：
	1. 子串：串中任意连续的字符组成的子序列。
	2. 主串：包含子串的串。
	3. 字符在主串中的位置：字符在串中的序号。是位置，不是下标。(第一次出现)
	4. 子串在主串中的位置：字串的第一个字符在主串中的位置。(第一次出现)

1.2 串VS线性表

1. 串是一种特殊的线性表，数据元素之间呈线性关系，且数据元素只能是字符。
2. 串的基本操作通常以子串为操作对象，而不是数据元素。

1.3 串的基本操作

1.4 串的分类

前面，我们已经知道了串是一种特殊的线性表，所以其分类，也就是三要素的分类和线性表差不多，具体分类如下：

* 物理结构
	1. 顺序存储
		1. 数组静态分配的串
		2. 数组动态分配的串
	2. 链式存储
		1. 静态链式串
		2. 动态链式串

1.5 小结

2. 串的存储结构

2.1 串的顺序存储

顺序串分为两种：数组静态分配的串和数组动态分配的串。如下图所示：

2.1.1 顺序串的四种实现方式

注意：在接下的讨论中，采用第四种方案。

2.1.2 数组静态分配的串

2.1.2.1 基本操作

2.1.2.1.1 求子串

2.1.2.1.2 比较操作

2.1.2.1.3 定位操作(BF算法)

因为定位操作是串的重点，这里，分析一下BF算法的时间复杂度：


可以得到其复杂度为O(n*m)，往往模式串比较短，相对于主串短很多，所以，又可以写成O(n)

2.1.3 数组动态分配的串

2.2 串的链式存储

链式串有两种：静态链式串和动态链式串。

注意：在链式存储的串中，我们一般会多存几个字符，以便提高存储密度。

2.2.1 链式串的两种实现方式

链式串有两种实现方式：

1. 带头结点
2. 不带头结点

2.2.2 链式串的两种实现

2.2.2.1 静态链式串

2.3 小结

3. KMP算法

3.1 KMP算法介绍

3.1.1 Why exit KMP

在上述串的定位操作中，我们使用的是传统的BF算法。这个算法有一个缺点：

• 当主串的某些子串能部分匹配时，主串中的扫描指针i会回溯的不够精准。当子串能部分匹配的情况比较多时，会导致时间开销增加。

如下图的子串gloglo与模式串glogle就是子串能部分匹配的情况：

从上图可以形象的看出BF算法的缺点：i指针回溯的不够精准。上图中子串匹配中BF算法比理想情况下多匹配了i = 2,3，即多进行了2次不必要的比较。当这种子串部分匹配的情况越多时，这种不必要的比较会更多。

而KMP算法就是针对BF算法的该缺点进行改进的：

• 当字串和模式串部分匹配时，主串的指针i不需要回溯，只需要调整模式串的指针j = next[j]。

注意：细心的同学可能注意到了，KMP算法回溯的指针是j不是i，后面会解释。

3.1.2 KMP的思想

首先，我们介绍两个术语：

1. 串的前缀：**包含第一个字符**，且**不包含**最后一个字符
2. 串的后缀：包含最后一个字符，且不包含第一个字符。

	* eg：串s = "abab"
		* s的前缀只有3个：“a”、“ab”、“aba”
		* s的后缀也只有3个：“b”、“ab”、“bab”

		* 注意：此时，我们可以得到串s的最长相同前后缀为"ab"

接下来介绍KMP算法的思想：

假设现在有如下字串部分匹配的情况：

接下来，我们的处理方式与BF算法不同，由于主串的指针i不能回溯，是j指针回溯，所以，我们需要移动模式串到前面部分相同的位置，由于我们不知道前面部分相同的位置在哪里，我们现在试着一步步移动模式串来达到目的：



此时i指向的？代表的非d字符可能是c，从而这个ab????子串可能与模式串相同。

而这整个过程就是在找当前字符前面的所有字符组成的串的最长相同前后缀。即找串s = "abcab"的最大前后缀，为"ab"。

那么，如果我们想让此次子串部分匹配的指针精准回溯，我们就应该找当前字符前面的所有字符组成的串的最长相同前后缀。如上图，刚开始时，j = 6，发现是部分匹配，那么j应该被重新赋值为j = 3, 此时3-1 = 2刚好与当前字符前面的所有字符组成的串的最长相同前后缀长度2相等。

注意：j指向向3而不是2，是因为j需要回溯到指向当前字符前面的所有字符组成的串的最长相同前后缀的下一个字符，这样能够尽最多的减少不必要的比较。

所以，进一步将问题转换，如果我们发现子串部分匹配时，想让此次子串部分匹配的指针精准回溯，我们应该令j = 当前字符前面的所有字符组成的串的最长相同前后缀的长度 + 1。
【注意：如果串的下标从0开始，j的回溯应该是 j = 令j = 当前字符前面的所有字符组成的串的最长相同前后缀的长度】

通常，我们会把模式串的每个字符前面的所有字符组成的串的最长相同前后缀的长度的值，事先求出来，放到一个next数组中。

比如，上图中模式串的next数组如下图所示：

注意：next[1]的值，应该与next[2,3,4...n]的值不冲突，即next[1] <= 0，而我们通常取next[1] = 0.

3.1.3 KMP部分代码

现在，你应该理解了上图的含义。但是目前还没有给出next数组的求法。然而，此时如果此时不考虑next数组里的值是如何求的，我们应该能够实现KMP算法了，具体代码如下：

注意：解释一下，上面的 j = 0.

1. 还记得本文中的串，我都是采用的这种格式，s[0]不存放字符：
   
2. 上述中j = 0，是由j = next[1]得到。而next[1]，表示在s[1]处，j指针已经指向模式串的第一个字符了，j往前面回溯不了了，所以给next[1]一个不存在的值，通常取0，因为我的s[0]没有字符。
   那么，当j取一个不存在的值，即j = 0时，我们需要让其从新指向s[1], 且i++.
3. 也不难想到，j = next[2]只能让回溯s[1]处，所以，next[2]的值必定为1。如果采用我这种串的结构的话。同理，如果是下面这种结构，则必须next[1] = 0
   
4. 到现在，应该懂了 j = 0，为什么要让他进入 i++,j++中，这样能够让 j = 1，从新指向第一个字符，同时i后移一个。
5. 那我现在举一个例子，让next[1] = -100，那么算法应该变为：
   

3.1.4 求next数组

好了，接下来，我们介绍如何手动计算next数组的值：

当第j个字符匹配失败，由前1~j-1个字符组成的串记为S，则：next[j] = S的最长相等前后缀长度 + 1。一般取next[0] = 0，这样就能计算出next数组的值。

下面是一个计算next数组的例子：

3.2 KMP算法的实现代码

KMP算法的实现比较巧妙，先给出实现，代码代码如下图所示：

上述代码的思想，还是使用的我们之前介绍的思想。求next数组的代码也是求最长相同前后缀的思想，下面我解释一下get_next()函数。

那么问题来了，为何一直令 k = next[k]，就能找到长度更短的相同前缀后缀呢？，可以利用对称性解释：

至此，我们就完成了对KMP算法的学习。还剩下一个问题，就是之前我说的，为什么精准回溯模式串的j指针，而不是主串的i指针？

其实，答案也很简单，你可以看到，我们对模式串的精准回溯是需要求next数组才能实现，如果是精准移动主串的i指针，那么我们对于每一个子串都需要求next数组，这样时间的开销基本没变，有时反而更费时间。而模式串是固定的，模式串通常都比较短，至少比主串短。我们只需要求一次next数组就可以了。

不得不说，有时候等价转换能将一些不能解决的事务解决，KMP算法就是将i指针回溯等价转换成了j指针回溯，从而解决了问题。

3.3 改进的KMP算法

你以为之前的KMP算法就是最优的吗？其实，KMP还有一种特殊情况会导致j指针回溯还是不够精准。这种情况就是：s[j] != s[i]; m = j; j = next[j]; 当s[m] == s[j]时，明显此时必定存在s[m] != s[i]，这样，我们完全可以这样：

具体做法就是，遍历next数组

1. 如果s[j] = s[next[j]], 则nextval[j] = nextval[next[j]],
2. 否则nextval[j] = next[j]

3.4 小结