C-CSL的密码（后缀数组-求本质不同的子串的数量）

https://ac.nowcoder.com/acm/contest/551/C

后缀数组LCP的应用

后缀数组两篇不错的blog
https://www.cnblogs.com/victorique/p/8480093.html
http://www.cnblogs.com/zwfymqz/p/8413523.html#_label5

求本质不同的子串的数量

枚举每一个后缀，第i个后缀对答案的贡献为len−sa[i]+1−height[i]

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define INF 0x3f3f3f3f;
#define fi first
#define se second
#define MP make_pair
#define PI pair<int,int>
#define lson l,m,rt<<1,ls,rs
#define rson m+1,r,rt<<1|1,ls,rs
#define test printf("here!!!\n")
using namespace std;
const int mx=1e5+10;
int n,m,maxn;
char s[mx];//rk可能存在相同的排名，但sa一定是不同的，因为位置是不同的（虽然不同位置的排名可能是一样的,但最后rk和sa肯定是不一样的，且可以有rk[sa[i]]=i,sa[rk[i]]=i的关系）
int sa[mx],tp[mx],rk[mx],rdx[mx],height[mx];//rk是sa的排行，然后第二关键字tp是依托于第一关键字sa进行排序的，即第一关键字优先于第二关键字
/*void Debug() {
    printf("*****************\n");
    printf("下标"); for (int i = 1; i <= n; i++) printf("%d ", i);     printf("\n");
    printf("sa  "); for (int i = 1; i <= n; i++) printf("%d ", sa[i]); printf("\n");
    printf("rk "); for (int i = 1; i <= n; i++) printf("%d ", rk[i]); printf("\n");
    printf("tp  "); for (int i = 1; i <= n; i++) printf("%d ", tp[i]); printf("\n");
}*/
void get_SA()
{
    for (int i=0;i<=m;++i) rdx[i]=0;
    for (int i=1;i<=n;++i) ++rdx[rk[i]];
    for (int i=1;i<=m;++i) rdx[i]+=rdx[i-1];
    for (int i=n;i>=1;--i) sa[rdx[rk[tp[i]]]--]=tp[i];
}
void SA()
{
    m=(int)'z';//m为不同字符子串
    for (int i=1;i<=n;++i) rk[i]=(int)s[i],tp[i]=i;
    get_SA();
    for (int w=1,p=0;p<n;m=p,w<<=1)
    {
        p=0;
        for (int i=n-w+1;i<=n;++i) tp[++p]=i;
        for (int i=1;i<=n;++i)
        {
            if (sa[i]>w) tp[++p]=sa[i]-w;
        }
        get_SA();
        swap(tp,rk);
        rk[sa[1]]=p=1;
        for (int i=2;i<=n;++i)
            rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&((sa[i-1]+w>n&&sa[i]+w>n)||(sa[i-1]+w<=n&&sa[i]+w<=n&&tp[sa[i-1]+w]==tp[sa[i]+w])))?p:++p;//此时的tp为之前的rk，即之前的rk排行,构造新rk
    }
    //for (int i=1;i<=n;++i) printf("%d ",sa[i]);
}
void getheight()//h[i]=height[rk[i]],height[i]=h[sa[i]],hight[rk[i]]=LCP(rk[i],rk[i]-1)
{
    int k=0;
    //for (int i=1;i<=n;++i) rk[sa[i]]=i;//上面结束时肯定是正确的rk
    for (int i=1;i<=n;++i)//按第i个位置来枚举
    {
        if (rk[i]==1) continue;
        if (k) --k;//h[i]>=h[i-1]-1
        int j=sa[rk[i]-1];
        while (i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) ++k;
        height[rk[i]]=k;
    }
    //for (int i=1;i<=n;++i) printf("%d ",height[i]);
}
int main()
{
    scanf("%d%d",&n,&maxn);
    scanf("%s",s+1);
    SA();
    getheight();
    ll ans=0;
    for (int i=1;i<=n;++i)
    {
        ans+=(n-sa[i]+1)-min(max(maxn-1,height[i]),n-sa[i]+1);
    }
    printf("%lld\n",ans);
}