---

前言

emmmm最近可能更得有点懒惰了，关于第三章过俩天补上。今天先复习第四章 串，串的大知识点其实也就是一个kmp模式串匹配，弄懂了这个就没什么大问题了。

---

一、串的定义*（非考点）

其实本来不打算介绍的，想想c和c++的不同还是说一下，c里面是没有string这个类型的，但是c++有。
字符串简称串，计算机上非数值处理的对象基本都是字符串数据。
串是由零个或多个字符组成的有限序列。一般记为
$$S{=}^{\prime }{a}_1{a}_2\cdot \cdot \cdot \cdot \cdot \cdot \cdot a_n^{\prime }(n>=0)$$
一般情况下，串可以用定长顺序表示、堆分配表示、块链存储表示。
适当地可以记一下串的一些操作的名称和作用：
1.StrCopy(&T,S):复制串S给T。
2.StrCmp(S,T):比较S,T，若S>T则返回>0，S=T则返回=T，否则返回<T。
3.Strlen(S):求字符串长度。
4.Concat(&T,S1,S2):串S1,S2连接返回给T。

二、★★★串的模式匹配（本章重点）

1.简单的模式匹配算法

以王道考研复习书上的例子来说，有模式串abcac和主串ababcabcacbab的匹配

比较传统简单暴力的方法就是每一次都从模式串的第一个字母开始比较而主串的指针后移一位，每一次比对到i和j的指针不相等就i=i-j+2,j=1。注意这里的i和j都是从1开始的，字符串0号位一般放长度。


等等，到第六次比较时候发现成功完全匹配。
简单模式匹配算法的最坏时间复杂度为O(mn)，其中m和n分别是主串和模式串的长度。

2.串的模式匹配算法——KMP算法

我们在传统的解决方案中，会发现其实有的时候感觉浪费时间了，但又说不上来，就明明看着感觉有时候可以一下挪好几个字母再开始比较，可是不知道应该怎么去表达，接下来要介绍的KMP算法就是为了解决这样的问题应运而生的。
如果没记错的话，KMP算法是由三位学者共同提出的，而取完名字首字母之后就叫KMP算法。
在介绍KMP算法之前，先简要概括一下KMP算法的最主要特征是：
主串的比较指针每一轮比较不再后移。只移动模式串的比较指针。
主串的比较指针每一轮比较不再后移。只移动模式串的比较指针。
主串的比较指针每一轮比较不再后移。只移动模式串的比较指针。
很重要很重要很重要！！！！

请首先分清楚模式串和主串

★串的前缀是指除最后一个字符以外，字符串的所有头部字串。
★串的后缀是指除第一个字符以外，字符串的所有尾部字串。
例如，ababa的最长前缀是aba，最长后缀也是aba，我们称最长相等前后缀长度的值为字符串的部分匹配值（Partial Match，PM）。一般都是对模式串求其部分匹配值。

每一个子串都一个部分匹配值，我们将其写下来（以上述模式串"abcac"，主串"ababcabcacbab"为例）

编号	1	2	3	4	5
S	a	b	c	a	c
PM	0	0	0	1	0

通过第一趟比较发现a和c不匹配，这时候，我们发现之前的第二趟比较的时候就不需要从主串的第二个字符b和模式串的第一个字符a比较了，没有必要，我们之前已经知道这俩个字符是什么了，作比较也是不相等然后继续后移。

所以这个时候我们只需要将模式串向后移动俩位即可

那么这个移动的位数呢，其实很容易找到规律，就是：
$$移动位数=已匹配的字符数-对应的部分匹配值$$

说简单点，其实就是我们做比较的时候，就已经比较过了的东西就没有必要重复比较。如果目前已匹配的字符的前后缀没有相等的地方，那么中间部分的比较也不可能会相同（例如abcd这个字符串，比较到d这里发现不一样，那么也就是说主串已匹配过的部分也是abc，模式串也是abc，接下来拿主串bc和后面一个接着的字符假设为e，也就是现在是bce和abc比较了，那么我们发现bc其实是上一次匹配的子串的后缀，而此时与bc比较的ab是上一次比较的子串的前缀部分，而abc子串的部分匹配值为0，说明子串的前缀和后缀没有相等的，所以接下来的比较毫无意义，直接跳过即可）。
如果有相等的部分，直接将模式串的最长前缀与主串的已匹配的子串的最长后缀对齐即可。这样就能省区一大把时间了QAQ。

那么以上如果看明白了，我相信对于下面介绍KMP的理解就简单多了。

上面的公式可以写出
$$Move=(j-1)-PM[j-1]$$
但是我们发现我们匹配失败的时候总是要找前一个匹配成功的部分匹配值，有点麻烦，那么我们干脆点直接将其整体右移（少的第一位以-1代替）

编号	1	2	3	4	5
S	a	b	c	a	c
next	-1	0	0	0	1

那么现在哪一位匹配失败，直接移动哪一位对应的next值就好了，也就是公式改写为：
$$Move=(j-1)-PM[j]，$$
相当于将子串的指针j回退到了next[j]+1的位置上，也就是此时j=next[j]+1，
注意，有的时候为了公式简洁、计算更加简单，我们将next数组整体加1，使其不出现负数

编号	1	2	3	4	5
S	a	b	c	a	c
PM	0	1	1	1	2

此时，j=next[j]。
意思就是，字串的第j个字符与主串发生不匹配的时候，将子串的j退回到next[j]的位置上与现在的主串的i继续进行比较，（因为前面介绍了说KMP的特点是主串的比较指针不会左移噢）。那么模式串移动到主串的最长后缀上，也可以理解为j指针回退到next[j]位置上继续比较（最长前后缀相等无需比较，所以j不需要回退完）。

假设之后应与模式中的第k个字符进行比较匹配，此时俩个串满足：
‘p₁p₂…p_k-1’=‘p_j-k+1p_j-k+2…p_j-1’

那么，next[j]和next[j-1]有什么关系呢？
当j=1的时候，，规定next[j]=0
当存在最长前后缀的时候，next[j]=max{k|1<k<j且’p₁Lp_k-1’=‘p_j-k+1Lp_j-1’}，也就是值就是最大部分匹配值+1，因为上面要保持有一项的话k-1=1，所以是2，也就是最大匹配值+1，也可以根据书上面的理解，若是再加一个p_k和p_j，若是俩者相等，那么表明在模式串的前缀和后缀中有，‘p₁p₂…p_k-1p_k’=‘p_j-k+1p_j-k+2…p_j-1p_j’，所以此时next[j]=next[j-1]+1=k+1;
其他情况就是next[j]=1

举个栗子

j	1	2	3	4	5	6	7	8	9
模式	a	b	a	a	b	c	a	b	a
next[j]	0	1	1	2	2	3	?	?	?

next[7]，我们观察到j=6的子串，发现没有最大部分匹配值，所以next[7]=1，满足第三个条件。（当然也可以认为，next[6]=3,p₆!=p₃,next[3]=1,p₆!=p₁,所以没有前后缀匹配）
next[8]，观察j=7的子串，最大部分匹配值为1，所以next[8]=1+1=2;(也可以认为next[7]=1,p₇=p₁,所以next[8]=next[7]+1)。
next[9]，观察j=8的子串，最大部分匹配值为2，所以next[9]=2+1=3。

3.KMP算法的进一步优化

再说一下KMP算法，将j回退到next[j]的位置上和当前的i进行比较
我们观察：
模式串’aaaab’和主串’aaabaaaab’进行匹配的时候，当i=4，j=4的时候，匹配失败，如果用之前的next数组还需要进行冗余的3次比较，因为每次都用相同的字符去比较毫无意义，p_next[4]=p₄=a,p_next[3]=p₃=a,p_next[2]=p₂=a，都不等于当前的i=4的字符(b)。

那有同学可能要说，哎，你这个怎么跟前面递推next数组那么像，不是等于了才能加一吗，别说，还真像，但一个是本位置的next值的位置上的字母和本位置的字母比，那个是上一个next推到下一个还是有区别的。

所以next数组其实还可以优化

主串	a	a	a	b	a	a	a	a	b
模式	a	a	a	a	b
j	1	2	3	4	5
next[j]	0	1	2	3	4
nextval[j]	0	0	0	0	4

我们将如果出现p_j=p_next[j]的情况下，我们将next[j]修正为next[next[j]]，直到俩者不相等为止。

---

总结

在学习KMP的时候，一定要理解前缀和后缀，单个字母是没有前后缀的，再思考KMP的优化思路，注意next数组可能会有时候，next[1]=0有时候为-1，注意题目要求就行。