SAテンプレート

saテンプレート(c++倍増)

void tsort() {
    memset(ws,0,sizeof(ws));int mx=0;
    fo(i,1,n) ws[x[y[i]]]++,mx=max(mx,x[y[i]]);
    fo(i,1,mx) ws[i]+=ws[i-1];
    fd(i,n,1) sa[ws[x[y[i]]]]=y[i],ws[x[y[i]]]--;
}
void getsa() {
    fo(i,1,n) y[i]=i,ws[x[i]]++;tsort();
    for(int j=1;j<=n;j*=2) {
        int k=0;fo(i,n-j+1,n) y[++k]=i;
        fo(i,1,n) if (sa[i]>j) y[++k]=sa[i]-j;
        tsort();
        fo(i,1,n) y[i]=x[i],x[i]=0;
        x[sa[1]]=1;k=1;
        fo(i,2,n) {
            if (y[sa[i-1]]!=y[sa[i]]||y[sa[i-1]+j]!=y[sa[i]+j]) k++;
            x[sa[i]]=k;
        }
        if (k==n) break;
    }
    fo(i,1,n) rank[sa[i]]=i;
}
void getheight() {
    int k=0;
    fo(i,1,n) {
        if (k) k--;
        int j=sa[rank[i]-1];
        while (i+k<=n&&j+k<=n&&st[i+k]==st[j+k]) k++;
        height[rank[i]]=k;
    }
}