后缀数组模板

#include<algorithm>

long wv[N],ws[N];

bool cmp(long *r,long a,long b,long len)
{
    return r[a]==r[b]&&r[a+len]==r[b+len];
}

void da(char *c,long *sa,long *rk1,long *rk2,long n,long m)
{
    long i,j,p;
    
    for (i=0;i<n;i++)ws[i]=0;
    for (i=1;i<=n;i++)ws[rk1[i]=c[i]-'a']++;
    for (i=1;i<m;i++)ws[i]+=ws[i-1];
    for (i=n-1;i>=0;i--)sa[--ws[rk1[i]]]=i;
    
    for (j=1,p=1;p<n;j<<=1,m=p){
        for (p=0,i=n-j;i<n;i++)rk2[p++]=i;
        for (i=0;i<n;i++)
            if (sa[i]>=j)rk2[p++]=rk1[i]-j;
        
        for (i=0;i<n;i++)wv[i]=rk1[rk2[i]];
        for (i=1;i<m;i++)ws[i]=0;
        for (i=0;i<n;i++)ws[wv[i]]++;
        for (i=1;i<m;i++)ws+=ws[i-1];
        for (i=n-1;i>=0;i--)sa[--ws[wv[i]]]=rk2[i];
        
        swap(rk1,rk2);
        rk1[sa[0]]=0;
        for (p=1,i=1;i<n;i++)rk1[sa[i]]=cmp(rk2,sa[i-1],sa[i],j)?p-1:p++;
    }
}