后缀数组

int n,m;
char s[N];
int sa[N]; // 排名第i位的是第几个后缀
int x[N]; // 第i个元素的第一关键字
int y[N]; // 第二关键字排名为i的数，第一关键字的位置
int height[N]; // sa[i]与sa[i - 1]的最长公共前缀
int rk[N]; // 第i个后缀的排名是多少
int c[N]; // 桶
void get_sa()
{
    for(int i = 1;i <= n;i++) ++c[x[i] = s[i]];
    for(int i = 2;i <= m;i++) c[i] += c[i - 1];
    for(int i = n;i;i--)sa[c[x[i]]--] = i;
    for(int k = 1;k <= n;k <<= 1)
    {
        int num = 0;
        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; // 第二关键字的位置为i+k,所以这里求第一关键字的位置要减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; //此时第一关键字的顺序已经排好,所以按照第二关键字的大小将第一关键字排好
        std::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;
    }
}
void get_height()
{
    for(int i = 1;i <= n;i++)rk[sa[i]] = i; // rk数组和sa数组是互逆的
    for(int i = 1,k = 0;i <= n;i++)
    {
        if(rk[i] == 1)continue; // 第一的height为0
        if(k) -- k; // h[i] >= h[i - 1] - 1     h[i]为第i个后缀与排名在第i个后缀前面一位的后缀的最长公共前缀
        int j = sa[rk[i] - 1]; 
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k])k++;
        //printf("%dn",k);
        height[rk[i]]  = k;
    }

}