文档介绍：Eentend Kmp 自动机 trie图 trie
字符串:KMP Eentend-Kmp自动机trie图trie树后缀树后缀数组(zz)2011-07-05 22:27
涉及到字符串的问题,无外乎这样一些算法和数据结构:自动机KMP算法Extend-KMP后缀树后缀数组trie树trie图及其应用。当然这些都是比较高级的数据结构和算法,而这里面最常用和最熟悉的大概是kmp,即使如此还是有相当一部分人也不理解kmp,更别说其他的了。当然一般的字符串问题中,我们只要用简单的暴力算法就可以解决了,然后如果暴力效率太低,就用个hash。当然hash也是一个面试中经常被用到的方法。这样看来,这样的一些算法和数据结构实际上很少会被问到,不过如果使用它们一般可以得到很好的线性复杂度的算法。
老实说,我也一直觉得字符串问题挺复杂的,出来一个如果用暴力,hash搞不定,就很难再想其他的方法,当然有些可以用动态规划。不过为了解决这个老大难问题,还是仔细对这些算法和数据结构研读了一番。做个笔记,免得忘了还得重新思考老长时间。如果碰到字符串问题,也一般不会超过这些方法的范围了。先看一张图吧,主要说明下这些算法数据结构之间的关系。图中黄色部分主要写明了这些算法和数据结构的一些关键点。
图中可以看到这样一些关系:extend-kmp是kmp的扩展;ac自动机是kmp的多串形式;它是一个有限自动机;而trie图实际上是一个确定性有限自动机;ac自动机,trie图,后缀树实际上都是一种trie;后缀数组和后缀树都是与字符串的后缀集合有关的数据结构;trie图中的后缀指针和后缀树中的后缀链接这两个概念及其一致。
下面我们来分别说明这些算法和数据结构,并对其涉及的关键问题进行分析和解释。
kmp
首先这个匹配算法,主要思想就是要充分利用上一次的匹配结果,找到匹配失败时,模式串可以向前移动的最大距离。这个最大距离,必须要保证不会错过可能的匹配位置,因此这个最大距离实际上就是模式串当前匹配位置的next数组值。也就是max{Aj是Pi的后缀j i},pi表示字符串A[],Aj表示A[]。模式串的next数组计算则是一个自匹配的过程。也是利用已有值next[-1]计算next[i]的过程。我们可以看到,如果A[i]=A[next[i-1]+1]那么next[i]=next[i-1],否则,就可以将模式串继续前移了。
整个过程是这样的:
void p(char*str){
int next[N+1];
int k=0;
next[1]=0;
//循环不变性,每次循环的开始,k=next[i-1]
for(int i=2;i=N;i++){
//如果当前位置不匹配,或者还推进到字符串开始,则继续推进
while(A[k+1]!=A[i]&&k!=0){
k=next[k];
}
if(A[k+1]==A[i])k++;
next[i]=k;
}
}
复杂度分析:从上面的过程可以看出,内部循环再不断的执行k=next[k],而这个值必然是在缩小,也就是是没执行一次k至少减少1;另一方面k的初值是0,而最多++N次,而k始终保持非负,很明显减少的不可能大于增加的那些,所以整个过程的复杂度是O(N)。
上面是next数组的计算过程,而整个kmp的匹配过程与此类似。
extend-kmp
为什么叫做扩展-kmp呢,首先我们看它计算的内容,它是要求出字符串B的后缀与字符串A的最长公共前缀。extend[i]表示B[]与A的最长公共前缀长度,也就是要计算这个数组。
观察这个数组可以知道,kmp可以判断A是否是B的一个子串,并且找到第一个匹配位置?而对于extend数组来说,则可以利用它直接解决匹配问题,只要看extend数组元素是否有一个等于len_A即可。显然这个数组保存了更多更丰富的信息,即B的每个位置与A的匹配长度。
计算这个数组extend也采用了于kmp类似的过程。首先也是需要计算字符串A与自身后缀的最长公共前缀长度。我们设为next数组。当然这里next数组的含义与kmp里的有所过程。但它的计算,也是利用了已经计算出来的next[-1]来找到next[i]的大小,整体的思路是一样的。
具体是这样的:观察下图可以发现
-1,要找到一个k,使得它满足k+next[k]-1最大,也就是说,让k加上next[k]长度尽量长。
实际上下面的证明过程中就是利用了每次计算后k+next[k]始终只增不减,而它很明显有个上界,来证明整个计算过程复杂度是线性的。如下图所示,假设我们已经找到这样的k,然后看怎么计算next[i]的值。设len=k+next[k]-1(图中我们用