后缀数组模板

#define F(x,y) for(int i=x;i<y;i++)
void bd(int m) {
    int *x=t1,*y=t2;
    F(0,m) c[i]=0; F(0,n) c[x[i]=s[i]]++; F(1,m) c[i]+=c[i-1]; F(0,n) sa[--c[x[i]]]=i;
    for(int p=1,k=1;p<n;k<<=1,m=p) {
        p=n;
        F(n-k,n) y[--p]=i; F(0,n) if(sa[i]>=k) y[--p]=sa[i]-k;
        F(0,m) c[i]=0; F(0,n) c[x[i]]++; F(1,m) c[i]+=c[i-1]; F(0,n) sa[--c[x[y[i]]]]=y[i];
        swap(x,y),p=1,x[sa[0]]=0;
        F(1,n) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
    }
    F(0,n) rk[sa[i]]=i;
    for(int i=0,j,k=0;i<n-1;ht[rk[i++]]=k)
    for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
}

需要注意的是，字符串末尾需要添加一个0（比字符串中所有字符都小的数），然后长度++。