1、计算机问题求解 论题4-11 - 串匹配,2017年5月3日,检查,模式P在文本T中以偏移3、11、35有效出现，是什么意思？如果我们说，一个有限自动机M接受字符串w。这是什么意思？,问题1:什么是 string-matching problem, 直观上? 形式上?,最容易想到的算法,问题2:为什么称它为“nave”算法？,问题3：为什么在最坏情况下复杂度是平方级的？,问题4：你能否说说nave算法有什么问题，为什么有可能改进？,最容易想到的算法,逐位单字符比较,问题5：Rabin-Karp算法的基本思想是什么？,Preprocessing,问题6:Rabin-Karp算法是采用“预处理”方
2、式的算法？何为“预处理”，这个算法预处理的结果是什么？,Matching,问题7：Rabin-Karp算法在“匹配”时拿什么与什么匹配？,这样有什么问题？是如何解决的？,问题8:对T中每个长度为m的子串在匹配前都必须计算它的“值”，这个计算是如何被“简化”的？,递推的方法,问题9：影响复杂度的关键是什么？,问题10：这是书上开始介绍Rabin-Karp算法时的第一段话，现在你能解释一下了吗？,有限状态机,问题11:你能将有限自动机与字符串的识别联系起来吗?,欲匹配的pattern一定是可接受的“语句”的后缀！,Whenever its current state q is a member o
3、f A, the machine M has accepted the string read so far. An input that is not accepted is rejected.,待匹配的pattern,问题12：你能否看出构建自动机的关键在哪里？,问题13：这个函数的“价值”在何处？,告诉我们“退”到那里。,如何构建自动机,问题14：(Pqa)究竟怎么确定？,后缀函数递归引理,问题15：你能解释右边的图吗？,确定(Pqa)与x无关，即与T无关。,可能需要代价m,问题16：能不能不计算转换函数？,KMP算法的基本思想,很显然，在我们只比较了5个字符，掌握了这些信息的基础上：,
4、偏移量s+1是必定是无效的！Why？,我们有没有办法确定哪个s偏移量可能是有效偏移？,为什么要问这个问题？,找到那个计算最小的s的线索,我们真正找的是P1.k在文本P1.q中的线索,s = s+(q-k),模式的前缀函数,KMP算法,KMP VS 有限状态机,问题：串匹配是否一定要查看T 中每一个字符？,Open Topics:Correctness of the prefix-function computationCorrectness of the KMP algorithm,课外作业,TC Ex.32.1-: 2, 3, 4TC Ex.32.2-: 1, 2, 3, 4TC Ex.32.3-: 2, 3, 5,
