后缀数组

从 Trac 迁移的文章

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

原文章内容如下：

 == 倍增模板 == 
{{{
//要保证最后一个是0（其实只要最后一个和其他的不一样就行了）
//最后rank和sa数组都是1到n的
//n要记得自减
//别忘了更改str数组的类型
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=200000+1;

int n;
char str[maxn];
int sa[maxn], rk[maxn];
int rs[maxn], ctn[maxn];
int height[maxn];

bool cmp0(int a, int b) { return str[a] < str[b]; }
int cmp(int a, int b, int l) { return rk[a] < rk[b] || rk[a+l] < rk[b+l]; }
void radix_sort(int l)
{
    int cnt = 0, i;
    for (i = n-1; i >= n-l; i--) ctn[cnt++] = i;
    for (i = 0; i < n; i++) if (sa[i] >= l) ctn[cnt++] = sa[i]-l;
    for (i = 0; i < n; i++) rs[i] = 0;
    for (i = 0; i < n; i++) rs[rk[i]]++;
    for (i = 1; i < n; i++) rs[i] += rs[i-1];
    for (i = n-1; i >= 0; i--) sa[--rs[rk[ctn[i]]]] = ctn[i];
    for (i = (ctn[*sa] = 0) + 1; i < n; i++)
        ctn[sa[i]] = cmp(sa[i-1], sa[i], l) + ctn[sa[i-1]];
    for (i = 0; i < n; i++) rk[i] = ctn[i];
}
void da()
{
    for (int i = 0; i < n; i++) sa[i] = i;
    sort(sa, sa+n, cmp0);
    for (int i = (rk[*sa] = 0) + 1; i < n; i++)
        rk[sa[i]] = cmp0(sa[i-1], sa[i]) + rk[sa[i-1]];
    for (int l = 1; rk[sa[n-1]] != n - 1; l <<= 1) radix_sort(l);
    for (int i = n-1; i >= 0; i--) rk[i] = rk[i-1], sa[i]++;
}
void make_height()
{
    int t = 0, p;
    for (int i = 1; i <= n; height[rk[i++]] = t)
        for (t?t--:0, p = sa[rk[i]-1]; str[i+t-1] == str[p+t-1]; t++) ;
}
}}}

 == 倍增模板（紧凑版） == 
{{{
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <ctime>
#define FORD(i,r,l) for(int i=(r);i>=(l);i--)
#define rep(i,n) for(int i=0;i<(n);i++)
#define req(i,l,n) for(int i=(l);i<(n);i++)
using namespace std;
const int maxn=100000+1;

int n;
char str[maxn];
int sa[maxn], *rk, initrk[maxn];
int rs[maxn], *ctn, initctn[maxn];
int height[maxn];

bool cmp0(int a, int b) { return str[a]<str[b]; }
int cmp(int a, int b, int l) { return rk[a]<rk[b]||rk[a+l]<rk[b+l]; }
void da()
{
    rk=initrk; ctn=initctn;
    rep (i,n) sa[i]=i;
    sort(sa,sa+n,cmp0);
    req (i,(rk[*sa]=0)+1,n)
        rk[sa[i]]=cmp0(sa[i-1],sa[i])+rk[sa[i-1]];
    for (int l=1,cnt;rk[sa[n-1]]!=n-1;l<<=1,swap(rk, ctn))
    {
        cnt=0;
        FORD (i,n-1,n-l) ctn[cnt++]=i;
        rep (i,n) if (sa[i]>=l) ctn[cnt++]=sa[i]-l;
        rep (i,n) rs[i]=0;
        rep (i,n) rs[rk[i]]++;
        req (i,1,n) rs[i]+=rs[i-1];
        FORD (i,n-1,0) sa[--rs[rk[ctn[i]]]]=ctn[i];
        req (i,(ctn[*sa]=0)+1,n)
            ctn[sa[i]]=cmp(sa[i-1],sa[i],l)+ctn[sa[i-1]];
    }
    FORD (i,n-1,0) rk[++sa[i]]=i;
}
void make_height()
{
    int t=0, p;
    for (int i=1;i<=n;height[rk[i++]]=t)
        for (t?t--:0,p=sa[rk[i]-1];str[i+t-1]==str[p+t-1];t++) ;
}
}}}

倍增模板

//要保证最后一个是0（其实只要最后一个和其他的不一样就行了）
//最后rank和sa数组都是1到n的
//n要记得自减
//别忘了更改str数组的类型
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=200000+1;
int n;
char str[maxn];
int sa[maxn], rk[maxn];
int rs[maxn], ctn[maxn];
int height[maxn];
bool cmp0(int a, int b) { return str[a] < str[b]; }
int cmp(int a, int b, int l) { return rk[a] < rk[b] || rk[a+l] < rk[b+l]; }
void radix_sort(int l)
{
    int cnt = 0, i;
    for (i = n-1; i >= n-l; i--) ctn[cnt++] = i;
    for (i = 0; i < n; i++) if (sa[i] >= l) ctn[cnt++] = sa[i]-l;
    for (i = 0; i < n; i++) rs[i] = 0;
    for (i = 0; i < n; i++) rs[rk[i]]++;
    for (i = 1; i < n; i++) rs[i] += rs[i-1];
    for (i = n-1; i >= 0; i--) sa[--rs[rk[ctn[i]]]] = ctn[i];
    for (i = (ctn[*sa] = 0) + 1; i < n; i++)
        ctn[sa[i]] = cmp(sa[i-1], sa[i], l) + ctn[sa[i-1]];
    for (i = 0; i < n; i++) rk[i] = ctn[i];
}
void da()
{
    for (int i = 0; i < n; i++) sa[i] = i;
    sort(sa, sa+n, cmp0);
    for (int i = (rk[*sa] = 0) + 1; i < n; i++)
        rk[sa[i]] = cmp0(sa[i-1], sa[i]) + rk[sa[i-1]];
    for (int l = 1; rk[sa[n-1]] != n - 1; l <<= 1) radix_sort(l);
    for (int i = n-1; i >= 0; i--) rk[i] = rk[i-1], sa[i]++;
}
void make_height()
{
    int t = 0, p;
    for (int i = 1; i <= n; height[rk[i++]] = t)
        for (t?t--:0, p = sa[rk[i]-1]; str[i+t-1] == str[p+t-1]; t++) ;
}

倍增模板（紧凑版）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <ctime>
#define FORD(i,r,l) for(int i=(r);i>=(l);i--)
#define rep(i,n) for(int i=0;i<(n);i++)
#define req(i,l,n) for(int i=(l);i<(n);i++)
using namespace std;
const int maxn=100000+1;
int n;
char str[maxn];
int sa[maxn], *rk, initrk[maxn];
int rs[maxn], *ctn, initctn[maxn];
int height[maxn];
bool cmp0(int a, int b) { return str[a]<str[b]; }
int cmp(int a, int b, int l) { return rk[a]<rk[b]||rk[a+l]<rk[b+l]; }
void da()
{
    rk=initrk; ctn=initctn;
    rep (i,n) sa[i]=i;
    sort(sa,sa+n,cmp0);
    req (i,(rk[*sa]=0)+1,n)
        rk[sa[i]]=cmp0(sa[i-1],sa[i])+rk[sa[i-1]];
    for (int l=1,cnt;rk[sa[n-1]]!=n-1;l<<=1,swap(rk, ctn))
    {
        cnt=0;
        FORD (i,n-1,n-l) ctn[cnt++]=i;
        rep (i,n) if (sa[i]>=l) ctn[cnt++]=sa[i]-l;
        rep (i,n) rs[i]=0;
        rep (i,n) rs[rk[i]]++;
        req (i,1,n) rs[i]+=rs[i-1];
        FORD (i,n-1,0) sa[--rs[rk[ctn[i]]]]=ctn[i];
        req (i,(ctn[*sa]=0)+1,n)
            ctn[sa[i]]=cmp(sa[i-1],sa[i],l)+ctn[sa[i-1]];
    }
    FORD (i,n-1,0) rk[++sa[i]]=i;
}
void make_height()
{
    int t=0, p;
    for (int i=1;i<=n;height[rk[i++]]=t)
        for (t?t--:0,p=sa[rk[i]-1];str[i+t-1]==str[p+t-1];t++) ;
}