//后缀数组模板
int wa[maxn]、wb[maxn]、wv[maxn]、ws[maxn]； //这些是必要的中间变量
intCMP(int*r，int a，int b，int l ) )。
{
return r[a]==r[b]r[a l]==r[b l]；
}
voidda(int*r，int *sa，int n，int m ) ) )。
//这里的n是字符串的长度为1，最后一位应该是附加的0。 这里主要是为了方便下一个height的求解，如果sa[0]出现在字符的中间，需要一些判断，感觉代码的复杂性增加了
//r是求出数组，sa是后缀数组
{
int i，j，p，*x=wa，*y=wb，*t；
//x首先收纳原来的数组，然后成为rank数组
//y对应于排序后的第二关键字的位置
for(I=0； I
for(I=0； I
for(I=1； I
for(I=n-1； i=0； I----sa[--ws[x[I]]]=I；
for(j=1，p=1； p
{
//在这两个阶段处理y，按照从小到大的顺序记录第二关键词的位置
for(p=0，i=n-j； I
for(I=0； i=j ) y[p ]=sa[i]-j； //这里对应sa[]，但在sa[]中要素被有序排序，所以直接代入值即可
for(I=0； I
for(I=0； I
for(I=0； I
for(I=1； I
for(I=n-1； i=0； I----sa[--ws[wv[I]]]=y[I]； //这里需要使用y[i]赋值。 y[]从小到大对应于第二关键字所在的位置
for(t=x，x=y，y=t，p=1，x [ sa [0] )=0，i=1； I
//上面的切换算法的作用是，将x排列的所有要素代入y，如果直接设定y=x，则x、y指向同一地址
x[sa[i]]=CMP(y，sa[i-1]，sa[I]，j )？ p-1:p； 将sa[]转换为rank，然后使用x[]进行保存。 p记录后缀字符串的不同个数，如果等于n就可以结束
}
返回；
}
求height[]，使用后缀数组
int rank[nMax]，height[nMax]；
intcalheight(int*r，int *sa，int n ) /这里的n是实际的字符串长度
{
int i，j，k；
for(I=1； i n； I ) rank[sa[i]]=i； 将sa[]更改为rank[]。 这里从1开始就可以了。 因为rank[sa[0]]始终为0
for(I=0； i n； height[rank[i ]]=k； 由于无法到达//n，即无法取得附加的0，因此可以避免rank[]为0，从而使下一个rank[i] - 1的运算变得容易
//h[i]=height[rank[i]]，h[i]=h[i - 1] - 1。 h[i]表示后缀数组suffix(i (与I之前邻接后缀数组的最长公共字符串
for(k？ k -- : 0，j=sa[rank[i] - 1]； r[i k]==r[j k]； k；
}
共享至：
2012-08-11 16:29
看713
注释