后缀数组

学习了鸡排...

终于可以不用sort了

顺便 压行压行压行

const int maxn = 1e6 + 10;
int n,k;
char s[maxn];
namespace Suffix_Array
{
    #define equ(x) (y[sa[i] + x] == y[sa[i - 1] + x])
    int rnk[maxn],tmp[maxn],sa[maxn],hei[maxn];
    int x[maxn],y[maxn],wc[maxn];
    void radix_sort(int m)
    {
        for(int i=1;i<=m;i++)wc[i] = 0;
        for(int i=1;i<=n;i++)wc[x[y[i]]]++;
        for(int i=1;i<=m;i++)wc[i] += wc[i - 1];
        for(int i=n;i>=1;i--)sa[wc[x[y[i]]]--] = y[i];
    }
    void makesa(char *s,int n,int m)
    {
        for(int i=1;i<=n;i++)x[i] = s[i],y[i] = i;radix_sort(m);
        for(int j=1,p=0;j<=n;j<<=1,m = p,p = 0)
        {
            for(int i=n-j+1;i<=n;i++)y[++p] = i;
            for(int i=1;i<=n;i++)
                if(sa[i] > j)y[++p] = sa[i] - j;
            radix_sort(m);swap(x,y);x[sa[1]] = p = 1;
            for(int i=2;i<=n;i++)x[sa[i]] = equ(0) && equ(j) ? p : ++p;
            if(p == n)break;
        }
        for(int i=1;i<=n;i++)rnk[sa[i]] = i;
        for(int i=1,k=0;i<=n;hei[rnk[i++]]=k)
            for(k ? k-- : 0;i+k<=n && s[i+k] == s[sa[rnk[i]-1]+k];k++);
    }
    int st[maxn][25],lg[maxn];
    void initST()
    {
        lg[0] = -1;lg[1] = 0;
        for(int i=2;i<=n;i++)lg[i] = lg[i >> 1] + 1;
        for(int i=1;i<=n;i++)st[i][0] = hei[i];
        for(int i=1;i<=lg[n];i++)
            for(int j=1;j + (1 << i) - 1<=n;j++)st[j][i] = min(st[j][i - 1],st[j + (1 << i - 1)][i - 1]);
    }
    inline int lcp(int u,int v)
    {
        if(u == v)return n - u + 1;
        u = rnk[u],v = rnk[v];
        if(u > v)swap(u,v);u++;
        int loog = lg[v - u + 1];
        return min(st[u][loog],st[v - (1 << loog) + 1][loog]);
    }
}
using namespace Suffix_Array;