KMP算法 6年前的6问复习

早就忘了，我直接搬出我6年前的问题压缩包，解压一遍就能再次学会。 Q1:子串从

已匹配的

第几个开始匹配是一定会错的呢？ A1:主串中与子串第一个字符不一样的(废话?) M1:每次都从主串中

已匹配的且

与子串第一个字符相等的开始吧，标记α。 M2:子串依M1执行，假设此时子串第二个字符为β，匹配主串

已匹配部分中α后跟着的所有β，并标记β。

依次类推，直到Mi找不到匹配的字符为止，那么这个M1到Mi找到的所有标记的部分就是

已匹配部分

对应的“最长不会错子串” Q2:那让你跳转一次，你选择跳到哪一个“最长不会错子串” A2:最后一个。因为已经知道“最长不会错子串”的后一个一定是匹配不上的，唯独最后一个的后一个字符是可能未被“考量”过的，是唯一有可能对的。 Q3:未被“考量”过的是什么情况？ A3:当

主串已匹配部分的后一个字符

成为最后一个“最长不会错子串”的后继字符时。 那么next数组就呼之欲出了，假如给Mi的结束条件更改为：子串找不到匹配的字符，并且该字符正好是

主串已匹配部分

的后继字符 那么假设

已匹配部分长度

为m，“最长不会错子串”长度为n，那么主串从子串下标为m-n-1位置继续匹配，记录一下next[m]=m-n-1。 那我只要把子串每前i个字符的next都算一下就行，O(P²/2):共P个字符，最好1次结束计算，最坏算一半P/2。共O(S+P²/2)≤O(SP)还行，就是没啥进步。 显然计算next花太多时间了，假设next[m]=m-n-1已经手算出来了，那么next[m+1]无非就是考虑在m个已匹配字符后再加一个字符后“最长不会错子串”的变化是啥。不妨把“最长不会错子串”的状态简单分类为“变长”和“变短”，它们是两个互斥量。 Q4:什么时候会“变长”? A4:当新加入的字符γ正好是子串下标为n的字符时，能增长一位，即 if(pattern[m-next[m]-1]==pattern[m]) next[m+1]=next[m]+1; Q5:显然不等的时候就会变短了，变短多少？ A5:不妨剪切最后一个“最大不会错子串”+一个后继字符作为新的子串，原子串变为主串，那么一定在后继字符处匹配失败，而新子串后继字符的下标就是n，此时新子串跳转的字符个数不正是next[n]吗(因为新子串与新主串开头是一样的，利用新主串算过的next数组就好) 此时新子串长度为n+1，减去next[n]再减一，就得到了一个字符的下标，n-next[n]，这个字符与后继字符比较一下，如果相等，就让next[m+1]=next[n-next[n]-1]+1，就像原主串和原子串的匹配一样。 如果不相等，就又可以剪切粘贴产生新新子串和新新主串，也就是有一个n-next[n]-1在更新，每次更新出一个新子串长度，它的长度一定是判别字符的下标加一：n-next[n]，因此只要不等，只需要令n=n-next[n]就行。 Q6:那这个递归过程的出口是什么？ A6: 1.找到相等的 2.next[m]=0，此时m不会再更新递归死了 3.next[m]<0，next定义可知遇不到 4.next[m]＞0，可正常递归 综上 else if(m-next[m]==0) next[m+1]=0 else m=m-next[m]; 换一个语义就有一种新写法，下次我掏出这6个问题时可能会想出不同的东西。 那只需要跑一遍子串就能算完next了，O(S+P)，完成分析任务。