后缀数组模板

后缀数组模板：

il void getsa(){
    int m=128;//初始m等于字符种类数
    for(int i=1;i<=n;i++)c[x[i]=s[i-1]]++;
    for(int i=2;i<=m;i++)c[i]+=c[i-1]; 
    for(int i=n;i;i--)sa[c[x[i]]--]=i;
    //x[i]是第i个元素的第一关键字 
    for(int k=1;k<=n;k<<=1){
        int num=0;//y[i]表示第二关键字为i的字符串第一关键字的位置 
        for(int i=n-k+1;i<=n;i++)y[++num]=i;//表示没有第二关键字的字符串，放在最前面 
        for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;//sa[i]>k表示sa[i]为sa[i]-k的第二关键字
        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)c[x[i]]++;
        for(int i=2;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y);x[sa[1]]=1;num=1;
        for(int i=2;i<=n;i++)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
        if(num==n)break;
        m=num;
    }
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
}
il void getheight(){
    int k=0;
    for(int i=1;i<=n;i++){
        if(rk[i]==1)continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(j+k<=n&&i+k<=n&&s[i+k-1]==s[j+k-1])k++;
        h[i]=k;
    }
    for(int i=1;i<=n;i++)height[rk[i]]=h[i];
}
//超级容易错，警惕啊！！每个数组的含义不能乱！菜哭辽