学了C/C++ 语言，我们已经会编程解题了，那怎么用来处理实际的问题呢？ 怎么设计数据结构来有效地管理企业人员？如何编写程序没让人才和岗位达到最佳匹配？如何安排旅行计划，找到最佳行程路径？这些学习、工作、生活中常常困扰我们的问题，你将在《数据结构基础》课程中找到答案。 数据结构是计算机程序设计的基础，告诉我们数据在计算机里是如何组织与存储的，能帮助我们刻画实际问题中的信息及其相互关系。当我们对一个实际问题本身有了一个结构化的认识之后，就可以选择合适的解决方法了。 完成这门课之时，你将掌握线性表、栈与队列、字符串、二叉树、树、图等经典的数据结构，并运用这些基础数据结构和相关算法解决实际应用问题。扎实的数据结构知识是项目开发与结构层次设计的关键，学好这门课会让你在高年级的计算机专业课程以及毕业项目设计中事半功倍，同时也将为你成为一名优秀的程序设计人员打下坚实的基础。 附：本课程的内容来自教材：《数据结构与算法》（张铭、王腾蛟、赵海燕 编著），高等教育出版社，2008年。
快速模式匹配KMP算法 （选修）
Loading...
来自 Peking University 的课程
数据结构基础
219 个评分
从本节课中
字符串
生活中不仅仅只有数值或单个字符，很多情况下，由若干个字符构成的字符串能表达更明确的信息。
在计算机中，字符串是如何存储的？有哪些相关操作？字符串常用的运算——模式匹配有哪些相关算法？你将会了解到字符串在计算机中的存储形式，常用的字符串操函数，以及模式匹配的一些高效的算法，并在实际问题中运用字符串处理技术。
重点：掌握字符串的基本概念（注意‘\0’结束符），KMP快速模式匹配。
难点：KMP快速模式匹配在一些重复子串问题中的应用。
与讲师见面
Prof. Ming Zhang 张铭教授
School of Electronics Engineering and Computer Science北京大学计算机系
大家好！
数据结构与算法，这一讲的内容是第四章字符串，其中的 快速模式匹配方法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算法呢，它是有预处理时间的，它预处理只须要到达ｍ,哦，
然后它的这个哦， 整个匹配呢，是到达ｎ.
当然因为这里其实是 哦，一个缺界，所以它们其实都可以用ｔｈｅｔａ来表示的。
感兴趣的同学可以去研究一下，其它的快速的模式匹配算法。
最后哦，留给大家这个思考。
在这个特征向量的求值中呢，其实有不同的规定。啊，就是有不同的这些方法。
那么这些不同的方法呢，它其实适合于一些不同的应用。
哦，我们可以去哦，比较一下一些而且实现它。
谢谢大家！
