后缀树和后缀数组

算法，可以在O(n)时间内进行预处理，每次询问可以在常数时间内完成。 对于一个固定的字符串S，其height数组显然是固定的，只要我们能高效地求出height数组，那么运用RMQ方法进行预处理之后，每次计算LCP(i,j)的时间复杂度就是常数级了。于是只有一个问题——如何尽量高效地算出height数组。 根据计算后缀数组的经验，我们不应该把n个后缀看作互不相关的普通字符串，而应该尽量利用它们之间的联系，下面证明一个非常有用的性质:为了描述方便，设h[i]=height[Rank[i]]，即height[i]=h[SA[i]]。h数组满足一个性质: 性质3:对于i>1且Rank[i]>1，一定有h[i]?h[i-1]-1。 根据性质3，可以令i从1循环到n按照如下方法依次算出h[i]: 若Rank[i]=1，则h[i]=0。字符比较次数为0。 若i=1或者h[i-1]?1，则直接将Suffix(i)和Suffix(Rank[i]-1)从第一个字符开始依次比较直到有字符不相同，由此计算出h[i]。字符比较次数为h[i]+1，不超过h[i]-h[i-1]+2。 否则，说明i>1，Rank[i]>1，h[i-1]>1，根据性质3，Suffix(i)和Suffix(Rank[i]-1)至少有前h[i-1]-1个字符是相同的，于是字符比较可以从h[i-1]开始，直到某个字符不相同，由此计算出h[i]。字符比较次数为h[i]-h[i-1]+2。 可以证明，这个求h[i]的算法复杂度是线性的。 求出了h数组，根据关系式height[i]=h[SA[i]]可以在O(n)时间内求出height数组，于是可以在O(n)时间内求出height数组。 结合RMQ方法，在O(n)时间和空间进行预处理之后就能做到在常数时间内计算出对任意(i,j)计算出LCP(i,j)。 因为lcp(Suffix(i),Suffix(j))=LCP(Rank[i],Rank[j])，所以我们也就可以在常数时间内求出S的任何两个后缀之间的最长公共前缀。这正是后缀数组能强有力地处理很多字符串问题的重要原因之一。 后缀数组与后缀树的比较 比较它们的空间: 后缀数组占用的空间比后缀树要小，刚才分析中我们并没有提到空间复杂度的问题，这里简单说一下:后缀数组SA和名词数组Rank都只需要n个整数的空间，而在由Rank计k算出SA的过程中需要用两个一维数组来辅助完成，各占n个整数的空间，滚动地进行操2k 作，整个算法只需要这四个一维数组和常数个辅助变量，因此总的空间占用为4n个整数。 而后缀树通常有2n个以上节点，通常每个节点要两个整数(即使采用一些技巧，至少还是要保存一个整数)，每个节点要有两个指针(假设采用儿子-兄弟表示方法)，因此总共的空间占用至少是4n个指针和2n个整数(至少是n个整数)。如果采用其他方法表示树状结构，需要的空间更大。可以看出后缀数组的空间需求比后缀树小。 比较它们的时间: 即使是用三分法，在线性时间复杂度内后缀数组，其速度还是比后缀树慢很多。 小结 后缀数组实际上可以看作后缀树的所有叶结点按照从左到右的次序排列放入数组中形成的，所以后缀数组的用途不可能超出后缀树的范围。甚至可以说，如果不配合LCP，后缀数组的应用范围是很狭窄的。但是LCP函数配合下的后缀数组就非常强大，可以完成大多数后缀树所能完成的任务，因为LCP函数实际上给出了任意两个叶子结点的最近公共祖先，这方面的内容大家可以自行研究。