大家好！
数据结构与算法，这一讲的内容是第四章字符串，其中的快速模式匹配方法KMP算法。
在快速匹配算法里面， 我们最主要的就是说，尽量的不要回溯。
KMP算法它实际上是一种无回溯的匹配方法。 一旦发生不等的时候，
我们怎样用P里面的哪一个字符pk和ti继续进行比较？
Knuth等人，
发现这个k值，仅仅依赖于模式本身，
而跟目标无关。我们来研究一下，这个匹配的过程。
对于这样的一个目标串，还有模式串，
他们前面的比较是，逐一相等的，
但是，在ti和pj位不等。如果是
朴素的匹配, 就会回到
ti-j+1这一位跟 p0继续比， 这样的一个匹配过程。
如果我们事先知道，
这个字串和这个字串，它不等。 这实际上
是首和尾的真子串。就是说我们发生不等的时候
盖住它。然后，看这个P, 模式，它的首尾的这个真子串。
它如果是说不等的话，我们下一趟比较就是没有意义的。 因为在很快就会发生不等。
继续往下头看。还有这样的一个
字串， 就是我们这个串长，它是，缩短了一个。
，但是，其实我们的优化，其实是往右面滑两位了。
如果是说它对应的也还是不等，它也没有必要继续比。
直到有一个k值，
这个k值，它是首尾串的这个真子串的长度。
使得我们前面的这个，首串的 k位和尾串的k位，它是
对应相等的。对于这样的一个
情况，既然是前面这个k位对应相等，
因为 p的这个尾串，它刚才
已经跟目标串进行过比较。我们就可以知道，
相应的p0跟这个ti-k, 还有pk-1
到ti-1，它们也是对应相等的。因此，就只须要
拿pk和ti来继续比较。
整个这个模式，它就可以优化j减k位，
来观察一下，字符串的特征向量。
这个特征向量，它其实是， 一组
整数值。也有些文献，把它叫做next数组。
我们来看它的这个构造方法。其实，就是
要寻找第j个位置它前面的
首尾真子串的，配串里面的最长的 另一个。
然后对其它的有些特殊情况，像j=0的时候，我们规定它等于-1. 这个是为了算法的方便。
啊，如果是说不存在这样的首尾的真子串，就是，
它的k值就是0。我们来看为什我们要找最长的一个？
下面是它的特征值。这个特征值里面，本来在
N=4这移位可以看到前面它的这个首尾的真子串，实际上是
等于3。
现在我们让它等于1。啊，等于1它也是对的。因为它是
就是说有这样的长度为1的首尾配串。
，但是，如果不是取得这个最大值3，
在某些情况我们就会，错过一些匹配。
例如我们在匹配到这一次的时候， P4，
发生不等的时候，我们可以看到。
因为我这里给的这个k值不是这个最大的一个，而是给的1。
我就会拿着P1来跟这个，
目标串里面的这个下标7, 来比较。
因此，它是一个非常大的一个滑动。就是ｊ减这个
k,所以是， 这个ｊ是等于4，然后k=1，就滑动3位。
其实本来是4-3，只能滑动１位。所以它就是错过了一个可能的
比较。好，我们来看一下这个KMP模式匹配
的这一个过程。对于这个模式我们求出了这个
特征向量。我们根据这个特征向量值，当
某一位发生不等的时候，直接查这个特征向量表。
然后拿出这个相应的这个，k值来。然后，就是
说这个Pk，直接跟刚才的这个，Ti进行比较。
噢，这个匹配的过程就完成了。它是非常迅速的。我们看， KMP模式匹配算法。
这个算法，我们假设它已经给了这样的一个特征向量， 然后，是从模式的第０位和 目标的指定的start位开始。
这个算法我们就是， 从这个ij这两个下标指向，
往后面走。如果是说相应的位子是相等的，就是，
i++, j++就是继续下一位的逐位比较。
如果是说在某一位
发现是j＝=-1了，实际上是碰到了
这个next是0的情况，就是说在这一位发生
不等。应该是把j+1，然后这个，
等于0，然后，i，也加一。 也就是说，目标，是换一个位子继续比较。
它也是没有回溯的。如果是说发生了不等的情况，我们这个j，就是
用特征向量里面的next j,也就是个k值。
啊，这个k值一定是小于j值的。啊，这个
P, j, 跟T, i 继续进行
比较。完成这个循环以后，如果这个j,它是
大于等于模式串的长度的，表示匹配是成功的。
否则，就是匹配失败。 对应的求特征向量的算法，
它是一个递归的这个过程。对于n0的情况，我们是
规定啊，它等于-1。然后假设
对于前面的若干位，也就是说ｊ之前的这个位，
我们都求出来了。假设我们是nj，它就等于k.
现在我们要求n j+1, 如果是说，
现在这个pj,它不等于pk,
这个时候，直接令k，等于nk.就是发生不等的时候，
我们用它前面的一个，特征来继续匹配。
所以这里其实可以看出它也是一个KMP的一个过程。就是前面是自己求出来，自己一个
子的特征向量，然后用这个子特征向量用来做这个匹配的过程。
好，一直到条件ｕｍ, 不满足，也就是说一直到pj等于pk，这样的情况。
这个时候，ｎｊ＋１，它等于k+1. 这样就是说这个特征
的向量，它的个首尾串，这个字串，它长度是加１的。
特征向量的一个算法就可以看出，首先对这些特殊的情况进行一下处理。
对于j=1的情况，其实也是可以用这个循环来，来求出来的。对于j=1,
它的特征向量值，其实就是等于0,因为，前面的
没有真的这个子串。
好！对于一个借它求出来的这样的一个值，这样的情况，
k值，是一致的。如果是， 当前这个，P[j]，
它不等于P[k]，我们就直接拿这个前面得到的
这个k的这个特征值来，
附给我们现在的这个k, 就是k = next[k]. 这个肯定是要变小的。因为，
k是小于next[k]的。j也是小于next[j]的。
啊，如果是相等的情况，就是说j++, k++,
往下面继续比。um,所谓配串长了是加了1。
而且，我们让这个next[j]它的值，是等于k。
这个实际上是已经加过1 的个k。
，这是求
特征向量的一个演示。我们可以看到，在求的过程中，
它都是要遮着自己，然后看前面的这个串的首尾真子串。
而且这些特征值，它的这些变化的过程，它都是渐变的，也就是顶多是加1加1
这样的变。当然如果是降，它是可以直接降到0，
或者是降到一个比这个3，比这个当前这个k 值小一些的，
这个数。我们看到它这个首尾串的匹配的过程。
这个算法它有没有优化的余地？就是说
我们来看一下，如果是说Pj=＝Pk的情况会怎样？
因为Pj=＝Pk而刚才，是
Pj，它不等于ti. 因此可以想像得到，你下一次用Pk
来跟ti来比，他其实是肯定不等的。因此这个是
可以，掠过去。这个不等的这个情况，我们可以直接的记录在特征数组里头。
我们来看这个例子。啊，这个例子里面，就是，相应的这个，
特征向量已经计算出来。当它P的3，
这一位发生 不等的时候，根据特征向量值，
它是用啊，这个K，等于0来比，也就是说P[0]，
这个，因为P[0]，它也是a, 它就等于这个P[3].
显然你刚才这里不等，它也是不会再相等的。所以这一行标红色的，它实际上是
冗余的一次比较。因此，可以做一些优化。这个优化，其实就是在这个地方，
也就是说如果是um, P[k]==P[j]的话，我们让它的这个next[j]直接，
直接等于next[k]. 因为j是大于k的，所以，它这样
的优化，它肯定是得到一个更小的这个k值。
我们看这个next数组，非优化版和优化版，它的差异。
啊，其实，可以看首先是求出这样的，
每一个特征位，它的首尾字串的，这样的，最长的k.
然后，我们的优化主要就是看它是不是 Pk==Pj？
如果等的话，我就直接让这个next[j]=next[k],
就做了这些优化。总体来说，这个，优化以后的这个next数组的
，特征值，它是比优化之前的些，它有一些位是要小一些的。
KMP算法的时间效率，
，我们虽然说看起来它像是一个双重循环， 但是，
在循环体里面，最重要的j=Next[j]这个语句，
它的执行的总次数是不能够超过ｎ次的。
因为每一次执行都会使得j要减少至少1。
对于j的增加的操作，只有j++这一次。
因此，如果是说j = N[j], 它的总的执行超出过n次的话，它必然会使得
j这个值，是会比-1 小很多。但是在整个算法里面，
其实只是在偶然的情况j变成-1,但是马上就加回到0。
因为这是，算法的一个处理的技巧。 因此，整个这个执行的过程，就是
大O(n)的，也就是KMP算法整个过程是大O(n)的。
对于这个特征向量的一个预处理过程，它实际上也是一个KMP的这样的一个过程。
因此，它的总的时间，是大O(m)的。所以它加起来m -> O(m)
大O(n+m)的。 我们总结一下，单模式匹配算法它的的时间效率。
我们主要说一下，朴素的和 KMP算法。朴素算法它不需要预处理，但它的，
模式匹配时间是大O(n*m).
对于这个KMP算法，它是有预处理时间的，它预处理只须要大O（ｍ）,，
然后它的这个， 整个匹配，是大O（ｎ）.
当然因为这里其实是 ，一个确界，所以它们其实都可以用ｔｈｅｔａ来表示的。
感兴趣的同学可以去研究一下，其它的快速的模式匹配算法。
最后，留给大家这个思考。
在这个特征向量的求值中，其实有不同的规定。就是有不同的这些方法。
这些不同的方法，它其实适合于一些不同的应用。
，我们可以去，比较一下一些而且实现它。
谢谢大家！