一套可用的后缀数组代码

十二月 6th, 2012 692 留下评论 阅读评论

后缀数组的代码算法难度比较高,反正没怎么看也不打算看懂,从网上找了好久找到一份比较好用的代码,效率也比较高,据说是用的倍增算法?看不懂 =.=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// r : 为字符串转化成的int数组, 0 - len-1 为源字符串, r[len] = 0
// sa : 1 - len有效, 值从0到len-1表示后缀序号
// rank : 0 - len-1有效, 值从1到len表示后缀字典序大小
// height : 2 - len有效, height[i] 为 sa[i]和sa[i-1]的LCP值
 
// da : n为字符串长度+1, m为字符集大小(用于基数排序)
// calh : n为字符串长度
 
#define MAX 40010
int height[MAX],rank[MAX],r[MAX],sa[MAX];
int ts[MAX],ta[MAX],tb[MAX],tv[MAX],pos;
bool cmp(int *y,int a,int b,int l){
    return y[a]==y[b]&&y[a+l]==y[b+l];
}
//计算sa和rank数组
void da(int n,int m){
    int i,j,*x=ta,*y=tb,p;
    for(i=0;i<m;i++) ts[i]=0;
    for(i=0;i<n;i++) ts[x[i]=r[i]]++;
    for(i=1;i<m;i++) ts[i]+=ts[i-1];
    for(i=n-1;i>=0;i--) sa[--ts[x[i]]]=i;
    for(j=1,p=1;p<n;j*=2,m=p){
        p=0;
        for(i=n-j;i<n;i++) y[p++]=i;
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0;i<m;i++) ts[i]=0;
        for(i=0;i<n;i++) tv[i]=x[y[i]];
        for(i=0;i<n;i++) ts[tv[i]]++;
        for(i=1;i<m;i++) ts[i]+=ts[i-1];
        for(i=n-1;i>=0;i--) sa[--ts[tv[i]]]=y[i];
        swap(x,y);
        x[sa[0]]=0;
        p=1;
        for(i=1;i<n;i++){
            if(cmp(y,sa[i-1],sa[i],j)) x[sa[i]]=p-1;
            else x[sa[i]]=p++;
        }
    }
}
//计算height数组
void calh(int n){
    int i,k,tmp;
    for(i=1;i<=n;i++) rank[sa[i]]=i;
    k=0;
    for(i=0;i<n;i++){
        tmp=sa[rank[i]-1];
        for(;r[i+k]==r[tmp+k];k++) ;
        height[rank[i]]=k;
        k?--k:0;
    }
}
 
 
int main(){
	int N, len;
	char line[MAX];
	while(scanf("%d", &N) != EOF && N > 0){
		getchar();
		gets(line);
		len = strlen(line);
		for(int i = 0;i < len;i++) r[i] = line[i] - 'a' + 1;	// 须保证r数组的值都 > 0
		r[len] = 0;
		da(len + 1, 27); // 27表示所有r数组内的值必须小于这个值, r从1到26 (基数排序)
		calh(len);
	}
}
Categories: 数据结构和算法 标签:
  1. 五月 12th, 2013 14:53

    这是倍增..

    • 这样啊 =.= 看不懂具体算法诶,只知道好用,嘿嘿

icon_wink.gif icon_neutral.gif icon_mad.gif icon_twisted.gif icon_smile.gif icon_eek.gif icon_sad.gif icon_rolleyes.gif icon_razz.gif icon_redface.gif icon_surprised.gif icon_mrgreen.gif icon_lol.gif icon_idea.gif icon_biggrin.gif icon_evil.gif icon_cry.gif icon_cool.gif icon_arrow.gif icon_confused.gif icon_question.gif icon_exclaim.gif