1.串的定义（不在大纲范围）
串，即字符串( String）是由零个或多个字符组成的有限序列
子串：串中任意个连续的字符组成的子序列。
主串：包含子串的串。
字符在主串中的位置：字符在串中的序号。
子串在主串中的位置：子串的第一个字符在主串中的位置。
串是一种特殊的线性表，数据对象限定为字符集，基本操作（增删改查）对象为子串
其中StrCompare(S, T)字符串比较操作实际上比较的是字符对应的二进制数的大小（ASCII码）
2.串的存储结构（不在大纲范围）
2.1.串的顺序存储
//静态数组方式 #define MAXLEN 255 // typedef struct{ char ch[MAXLEN]; //静态分配一个数组，数组每个元素存储一个字符 int length; //串的实际长度 }sString; //动态分配方式，使用完后要手动free typedef struct{ char *ch; //按串长度分配空间，ch指向串的首地址 int length; //串的实际长度 }hString; hString str; str.ch = (char*)malloc(MAXLEN * sizeof(char)); str.length = 0;
2.2.串的链式存储
typedef struct stringNode{ //因为*next指针的大小为4，如果ch元素的个数过低，则存储密度就低 char ch[4]; struct stringNode *next; }stringNode, *string;
3.朴素模式匹配
算法思想：从S的首个字符开始选取与T相同长度的字符内容，逐一与T的字符串内容进行匹配。如果有任意一个字符不同，则进行下一轮匹配；如果都相同，则结束循环，返回进入循环的S的字符的地址
最坏时间复杂度：O(mn)
int index(sString S, sString T){ int k = 1; int i = k, j = 1; //遍历S和T while (i <= S.length && j <= T.length){ //当前s和t的字符相同，则继续匹配 if (S.ch[i] == T.ch[j]){ i++; j++; } //当前s和t的字符不相同，则k向后移动，从k处继续下一轮循环 else{ k++; i = k; j = 1; } } //s和t相同，则返回k if (j > T.length) return k; else return 0; }
缺点：没有考虑到子串和主串的在匹配中可能含有公共前缀，需要经常回溯
4.kmp算法（选择题）
改进思路：
1.主串指针不回溯，只有模式串指针回溯
2.当j = k时，匹配失败，说明前k - 1个元素是匹配成功的，因此，可以将模式串指针（主串指针不动）移动到下一个已经匹配成功部分的模式串（子串）中的最大公共前后缀的位置上
串的前缀：包括第一个字符，且不包括最后一个字符的子串（即不包括自身）
串的后缀：包含最后一个字符，且不包含第一个字符的子串（即不包括自身）
next数组：当j = k时，匹配失败，前k - 1个字符组成的字符串记为S，next[j] = S的最长相等前后缀长度+1（S自身比较）。特别的，next[1] = 0，next[2] = 1（任何模式串）
1.next[1] = 0的含义是设主串的匹配指针为i，模式串的匹配指针为j，next[1]出现的场合是模式串和主串的第一次匹配就失败，此时，执行操作：j = next[j] 即j = next[1] = 0，执行完后执行i++，j++就可以直接重新对主串的下一个元素和模式串的第一个元素进行匹配
2.next[2]的求法是：设字符串为abab，j = 2，即需要求a的最长相等前缀后缀，因为前缀不包含最后一个字符，后缀不包含第一个字符，因此，最长相等前后缀为0，next[2] = a的最长相等前后缀长度 + 1 = 0 + 1 = 1
3.为什么next[j] = S的最长相等前后缀长度+1中，需要+1：如果不+1，仅仅是移动到最长相等前后缀的最后一个元素，而我们需要进行匹配的是下一个元素
例：主串：ABABBA 模式串：ABAA i为主串工作指针，j为模式串工作指针
当i = 4，j = 4时，匹配失败，模式串的最长相等前后缀长度为1，如果不加1，j = next[j] = 1，这样就会回到A，而按照kmp算法的思想A不需要再次进行匹配，我们需要进行的下次匹配是模式串的B
时间复杂度O(m+n)
5.kmp算法的改进
以王道书图中的例子为例。
- j = 4 指向a，i = 4 指向b时，匹配失败，则 j = next[4] = 3
- 进行下一轮匹配：j = 3 指向a，i = 4 指向b，匹配失败，则 j = next[3] = 2
- 进行下一轮匹配：j = 2 指向a，i = 4 指向b，匹配失败，则 j = next[2] = 1
- 进行下一轮匹配：j = 1 指向a，i = 4 指向b，匹配失败，则 j = next[1] = 0
- 进行下一轮匹配：j++，i++，j = 1 指向a，i = 5 指向a
从中可知，2 - 5的匹配结果其实是已知的，因为在 1 的时候就已经进行过一次模式串为a，主串为b的匹配，因此，2 - 5的匹配实际上是可以进行优化的
改进方法：在next数组的基础上，如果出现匹配失败的情况，需要多进行一次 j 指向的模式串元素是否与更新后 j = next[j] 指向的元素相等的判断，如果两者相等，则继续递归进行 j = next[next[j]]，直至两者不相等为止，然后将结果更新为nextval数组
6.王道课后题
- next[1]出现在模式串的第一个元素与主串当前元素匹配失败的情况下，将模式串的工作指针归零，然后进行j++和i++操作，从头开始匹配模式串和主串的下一个元素
- 取模式串中最大相等前后缀的长度作为模式串右移的距离，k的最大值是j - 1，因为前缀不包括最后一个字符，后缀不包括第一个字符
- 其他情况是模式串的最大相等前后缀仅为第一个字符和最后一个字符，取next[j] = 1就是直接 j 移动到模式串的最后一个字符的当前位置，模式串从第一个位置，主串从第i个位置进行匹配
解：除了next[1]不固定+1外（需要从头开始匹配模式串和子串），所有next数组都要固定 + 1，表示从模式串和子串的公共前后缀的下一个字符开始匹配（公共前后缀的意义就是将模式串某些前缀和后缀相同，在公共前后缀的前缀+1处匹配失败后，不需要匹配，直接快速移动到公共前后缀的后缀+1处进行下次匹配）
- j = a, next[1] = 0（next[1]从头开始匹配模式串和子串，固定为0）
- j = a a, next[2] = 0 + 1 = 1（前缀不能包括最后一个字符，后缀不能包括第一个字符）
- j = aa b, next[3] = 1 + 1 = 2（公共前后缀长度为1）
- j = aab a, next[4] = 0 + 1 = 1（第一个字符为a，最后一个字符为b，没有公共前后缀）
- j = aaba a, next[5] = 1 + 1 = 2
- j = aabaa c, next[6] = 2 + 1 = 3
2.解：next[j]的j代表取模式串的前j个字符计算公共前后缀
- i = 1 = a, j = 1 = a, 匹配成功 i++, j++
- i = 2 = a, j = 2 = a, 匹配成功 i++, j++
- i = 3 = b, j = 3 = b, 匹配成功 i++, j++
- i = 4 = a, j = 4 = a, 匹配成功 i++, j++
- i = 5 = a, j = 5 = a, 匹配成功 i++, j++
- i = 6 = b, j = 6 = c, 匹配失败 j = next[j] = 3
- i = 6 = b, j = 3 = b, 匹配成功 i++, j++
- i = 7 = a, j = 4 = a, 匹配成功 i++, j++
- i = 8 = a, j = 5 = a, 匹配成功 i++, j++
- i = 9 = b, j = 6 = c, 匹配失败 j = next[j] = 3
- i = 9 = b, j = 3 = b, 匹配成功 i++, j++
- i = 10 = a, j = 4 = a, 匹配成功 i++, j++
- i = 11 = a, j = 5 = a, 匹配成功 i++, j++
- i = 12 = c, j = 6 = c, 匹配成功 i++, j++
- i > 模式串长度 结束循环 return true
