后缀数组

 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
namespace SA
{
    static const int Sigma=127;
    int rk[MAX],sa[MAX],olrk[MAX<<1],buc[MAX];
    int id[MAX],pid[MAX],height[MAX];
    char s[MAX]; int n;

    inline void Build()
    {
        n=strlen(s+1);
        for(int i=1;i<=n;++i) ++buc[rk[i]=s[i]];
        for(int i=1;i<=Sigma;++i) buc[i]+=buc[i-1];
        for(int i=n;i;--i) sa[buc[rk[i]]--]=i;
        for(int w=1,m=Sigma,p=0;;w<<=1,m=p,p=0)
        {
            for(int i=n;i+w>n;--i) id[++p]=i;
            for(int i=1;i<=n;++i) if(sa[i]>w) id[++p]=sa[i]-w;
            for(int i=1;i<=m;++i) buc[i]=0;
            for(int i=1;i<=n;++i) ++buc[pid[i]=rk[id[i]]];
            for(int i=1;i<=m;++i) buc[i]+=buc[i-1];
            for(int i=n;i;--i) sa[buc[pid[i]]--]=id[i];
            p=0;
            for(int i=1;i<=n;++i) olrk[i]=rk[i];
            for(int i=1;i<=n;++i) p+=(olrk[sa[i]]!=olrk[sa[i-1]]||olrk[sa[i]+w]!=olrk[sa[i-1]+w]),rk[sa[i]]=p;
            if(p==n) break;
        }
    }
    inline void GetHeight()
    {
        for(int i=1,k=0;i<=n;++i)
        {
            for(k=max(k-1,0ll);s[i+k]==s[sa[rk[i]-1]+k];++k);
            height[rk[i]]=k;
        }
    }
}