luoguP2408不同子串个数

传送门

可以知道每一个子串都是后缀的前缀，那么对于第\(i\)小的后缀的贡献就可以表示为n-sa[i]+1
然而会存在重复的子串，注意height数组的定义，对于sa[i-1]和sa[i]，只有height[i]个子串会被重复计算，每次都减掉就好了
代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
    char ch; bool ok;
    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e5+10;long long ans;
int n,a[maxn],m='z',x[maxn],y[maxn],num,sa[maxn],rk[maxn],h[maxn];char p[maxn];
int main()
{
    read(n);scanf("%s",p+1);
    for(rg int i=1;i<=n;i++)a[x[i]=p[i]]++;
    for(rg int i=1;i<=m;i++)a[i]+=a[i-1];
    for(rg int i=n;i;i--)sa[a[x[i]]--]=i;
    for(rg int k=1;k<=n;k<<=1,num=0)
    {
        for(rg int i=n-k+1;i<=n;i++)y[++num]=i;
        for(rg int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
        for(rg int i=1;i<=m;i++)a[i]=0;
        for(rg int i=1;i<=n;i++)a[x[i]]++;
        for(rg int i=1;i<=m;i++)a[i]+=a[i-1];
        for(rg int i=n;i;i--)sa[a[x[y[i]]]--]=y[i];
        for(rg int i=1;i<=n;i++)y[i]=x[i];
        num=x[sa[1]]=1;
        for(rg int i=2;i<=n;i++)
            if(y[sa[i]]!=y[sa[i-1]]||y[sa[i]+k]!=y[sa[i-1]+k])x[sa[i]]=++num;
            else x[sa[i]]=num;
        if(num>=n)break;m=num;
    }
    for(rg int i=1;i<=n;i++)rk[sa[i]]=i;
    for(rg int i=1,k=0,j;i<=n;h[rk[i++]]=k)
        for(k=k?k-1:k,j=sa[rk[i]-1];p[j+k]==p[i+k];k++);
    for(rg int i=1;i<=n;i++)ans+=n-sa[i]-h[i]+1;printf("%lld\n",ans);
}

luoguP2408不同子串个数

原文：https://www.cnblogs.com/lcxer/p/10457475.html