昨天上课讲了kmp算法 虽然上课的时候老师讲的不明白 但是好歹课下课把kmp理解透了 这个算法还是比较适合举例来说 抛开实例讲概念 用什么i-1、d之类的说太混乱了 看到很多人都讲kmp，我也来说说 也算留个底 方便以后翻阅
首先是算法的功能 谈到功能就不得不先谈暴力算法 KMP算是改进暴力算法的算法 这两种算法的功能是根据已知的模式串 从目标串中找出与模式串完全匹配的字段 暴力算法之所以叫做暴力算法 就是因为是以穷举为基本思想 从头到尾一个一个匹配 遇见不匹配时向后跳一位 而自古以来 穷举法就是算法改进的火车头 哪里有穷举法 哪里就有算法改进 KMP自然就是暴力算法的改进
KMP算法与暴力算法功能相同 他的核心思想是检测不匹配位置之前已匹配位置的字符排列 使模式串向后寻找下一个位置的匹配时 可以不必一位一位跳 直接向后跳多位 就实现了算法的优化 从O(n*m)优化为O(m+n)
暴力算法在某一位不合适的时候 全部跳向下一位 KMP在不合适的时候 先查找不匹配之前的项 原理是这样的 如果模式串ababa 目标串ababc 在第4位不匹配 则寻找一个位置 使得能跳过几个位置 这个位置就是模式串的第2位 由于第4位不匹配 而第01和第23位是相同的 已知这个位置就能做到跳过一部分的无用比较 这个位置被称作next[i]数组 其中i为模式串与目标串不匹配的位数 next[i]的数值为除最后一位的前提下从头算起和从尾算起的完全最大真子串的数值 在全不相等时时next=0, 并规定next[0]=-1 举例说明：ababaa next[0]=-1 next[1]=0 ab中仅有a一个数 无最大真子串 next[2]=0 a和b 不等 next[3]=1 a,ab和a,ba 相等的最大真子串为含一个数 next[4]=2 a,ab,aba和b,ab,bab 相等的最大真子串含两个数 next[5]=3 a,ab,aba,ababa和a,ba,aba,baba 相等的最大真子串含三个数 这样就很清楚了
然后是KMP的优化算法 精髓是nextval[i]数组 例如在模式串aaab 目标串aaaaba中 按KMP算法 还是会一位一位跳动至模式串第0为匹配目标串第5位 这也是不必要的 通过nextval可以直接使模式串第0位匹配目标串第5位 nextval[i]的数值也是模式串的新位置对应不匹配位置 这个位置是这样定义的： 当第i位和第next[i]位是相同的字符时，nextval[i]=nextval[next[i]]；不同时则nextval[i]=next[i]，并定义nextval[0]=-1 如果两位不等的话，就还是需要那一位置来匹配；如果相等时，就去找next[i]位的nextval值。 还是上面的例子 nextval[0]=-1 nextval[1]=0 0和1位不同，故和next[1]相等 nextval[2]=-1 2和0位相等，故nextval[2]=nextval[next[2]]=0 nextval[3]=0 3和1位相等，故为1 nextval[4]=-1 4和2位相等，故为-1 nextval[5]=-1 5和3位不等，故为3
KMP算法这部分说考试就只考next和nextval的计算 别的不考 对于原理其实不要求 对程序实现更不要求 但是还是要看看程序实现
老师讲这部分讲的很乱 本以为自己可以说得清 结果也是很混乱 说的一头雾水 其实结合抽象图和实例还是很好说的 但是画图不方便 更不能从其他人处盗图 所以就先这样吧
