2013-team5/Suffix-array

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;
typedef long long LL;
const int MN=1e6+7;

int T[MN],sa[MN],tsa[MN],rank[MN*2],trank[MN],c[MN],height[MN];

void bsort(int k,int n){ /* 双关键字基数排序 */
    int i;
    memset(c,0,sizeof(c)); /* 以第二关键字基数排序 */
    for (i=0; i<n; i++) c[rank[i+k]]++;
    for (i=1; i<n; i++) c[i]+=c[i-1];
    for (i=n-1; i>=0; i--) tsa[--c[rank[i+k]]]=i;
    memset(c,0,sizeof(c)); /* 以第一关键字基数排序 */
    for (i=0; i<n; i++) c[rank[i]]++;
    for (i=1; i<n; i++) c[i]+=c[i-1];
    for (i=n-1; i>=0; i--) sa[--c[rank[tsa[i]]]]=tsa[i];
    /* 这样相当于，当第一关键字相同时，采用通过第二关键字排的顺序 */
}
void getsa(int *T,int *sa,int n){
    int i,k,p;
    memset(rank,0,sizeof(rank));
    memset(c,0,sizeof(c));
    for (i=0; i<n; i++) c[T[i]]++;
    for (i=1; i<max(n,128); i++) c[i]+=c[i-1]; /* n可能小于字符种类数 */
    for (i=n-1; i>=0; i--) sa[--c[T[i]]]=i;
    rank[sa[0]]=p=1; /* Notice! */
    for (i=1; i<n; i++) rank[sa[i]]=(T[sa[i]]==T[sa[i-1]])?p:++p;
    for (k=1; k<=n && p<n; k<<=1){
        bsort(k,n);
        trank[sa[0]]=p=1;
        for (i=1; i<n; i++)
            trank[sa[i]]=(rank[sa[i-1]]==rank[sa[i]] && rank[sa[i-1]+k]==rank[sa[i]+k])?p:++p;
        for (i=0; i<n; i++) rank[i]=trank[i];
    }
}

void getheight(int* T,int* sa,int *height,int n){
    int i,j,k;
    for (i=0; i<n; i++) rank[sa[i]]=i;
    k=0; height[0]=0; 
    for (i=0; i<n; i++){
        if (k) k--;
        if (rank[i]==0) continue;
        int j=sa[rank[i]-1];
        while (T[i+k]==T[j+k]) k++;
        height[rank[i]]=k;
    }
}    /* height[i]表示sa[i-1]与sa[i]的最长公共前缀长度, 其中height[0]=0 */
}}}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long LL;
const int MN=1e6+7;
int T[MN],sa[MN],tsa[MN],rank[MN*2],trank[MN],c[MN],height[MN];
void bsort(int k,int n){ /* 双关键字基数排序 */
    int i;
    memset(c,0,sizeof(c)); /* 以第二关键字基数排序 */
    for (i=0; i<n; i++) c[rank[i+k]]++;
    for (i=1; i<n; i++) c[i]+=c[i-1];
    for (i=n-1; i>=0; i--) tsa[--c[rank[i+k]]]=i;
    memset(c,0,sizeof(c)); /* 以第一关键字基数排序 */
    for (i=0; i<n; i++) c[rank[i]]++;
    for (i=1; i<n; i++) c[i]+=c[i-1];
    for (i=n-1; i>=0; i--) sa[--c[rank[tsa[i]]]]=tsa[i];
    /* 这样相当于，当第一关键字相同时，采用通过第二关键字排的顺序 */
}
void getsa(int *T,int *sa,int n){
    int i,k,p;
    memset(rank,0,sizeof(rank));
    memset(c,0,sizeof(c));
    for (i=0; i<n; i++) c[T[i]]++;
    for (i=1; i<max(n,128); i++) c[i]+=c[i-1]; /* n可能小于字符种类数 */
    for (i=n-1; i>=0; i--) sa[--c[T[i]]]=i;
    rank[sa[0]]=p=1; /* Notice! */
    for (i=1; i<n; i++) rank[sa[i]]=(T[sa[i]]==T[sa[i-1]])?p:++p;
    for (k=1; k<=n && p<n; k<<=1){
        bsort(k,n);
        trank[sa[0]]=p=1;
        for (i=1; i<n; i++)
            trank[sa[i]]=(rank[sa[i-1]]==rank[sa[i]] && rank[sa[i-1]+k]==rank[sa[i]+k])?p:++p;
        for (i=0; i<n; i++) rank[i]=trank[i];
    }
}
void getheight(int* T,int* sa,int *height,int n){
    int i,j,k;
    for (i=0; i<n; i++) rank[sa[i]]=i;
    k=0; height[0]=0; 
    for (i=0; i<n; i++){
        if (k) k--;
        if (rank[i]==0) continue;
        int j=sa[rank[i]-1];
        while (T[i+k]==T[j+k]) k++;
        height[rank[i]]=k;
    }
}    /* height[i]表示sa[i-1]与sa[i]的最长公共前缀长度, 其中height[0]=0 */