大家好！ 数据结构与算法，这一讲的内容是第四章字符串，其中的 快速模式匹配方法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来继续比较。 整个这个模式，它就可以右滑借减k位， 那来观察一下，字符串的特征向量。 那这个特征向量呢，它其实是哦， 一组 整数值。那也有些文献呢，把它叫做next数组。 那我们来看它的这个构造方法。那其实呢，就是 要寻找递接着位置它前面的 首尾真字串的，配串里面的最长的 另一个。 然后对其它的有些特殊情况，像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直接呢， 直接等于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。 因为这是哦，算法的一个处理的技巧。 因此呢，整个这个执行的过程呢，就是 哦，倒n的，也就是KMP算法整个过程是到n的。 那对于这个特征向量的一个预处理过程，它实际上也是一个KMP的这样的一个过程。 因此，它的总的时间呢，是到m的。所以它加起来是到达 n+m的。 那我们总结一下，单模式匹配算法它的的时间效率。 那我们主要说一下，朴素的和 KMP算法。那朴素算法它不需要预处理，但它的， 模式匹配时间是到达n乘m. 对于这个KMP算法呢，它是有预处理时间的，它预处理只须要到达ｍ,哦， 然后它的这个哦， 整个匹配呢，是到达ｎ. 当然因为这里其实是 哦，一个缺界，所以它们其实都可以用ｔｈｅｔａ来表示的。 感兴趣的同学可以去研究一下，其它的快速的模式匹配算法。 最后哦，留给大家这个思考。 在这个特征向量的求值中呢，其实有不同的规定。啊，就是有不同的这些方法。 那么这些不同的方法呢，它其实适合于一些不同的应用。 哦，我们可以去哦，比较一下一些而且实现它。 谢谢大家！
