不同子串个数

题目背景

因为NOI被虐傻了，蒟蒻的YJQ准备来学习一下字符串，于是它碰到了这样一道题：

题目描述

给你一个长为N的字符串，求不同的子串的个数

我们定义两个子串不同，当且仅当有这两个子串长度不一样或者长度一样且有任意一位不一样。

子串的定义：原字符串中连续的一段字符组成的字符串

输入格式

第一行一个整数N

接下来一行N个字符表示给出的字符串

输出格式

一行一个整数，表示不一样的子串个数

输入输出样例

输入 #1
5
aabaa
输出 #1
11
输入 #2
3
aba
输出 #2
5

说明/提示

请使用64位整数来进行输出

（具体来说，C++和C选手请使用long long 类型，pascal选手请使用Int64）

由于输入文件过大，请使用高效的读入方法（具体的，c++和c选手请不要使用cin，pascal选手不需要管）

对于30%的数据，

对于100%的数据， $10^5N≤105$

#include<bits/stdc++.h>
const int N = 4e5+50;
using namespace std;

struct SuffixArray
{
    int sa[N],rank[N],height[N],cnt[N],a1[N],a2[N],n,m,*x,*y;
    void sort()
    {
        for(int i=0; i<m; i++) cnt[i]=0;
        for(int i=0; i<n; i++) cnt[x[i]]++;
        for(int i=1; i<m; i++) cnt[i]+=cnt[i-1];
        for(int i=n-1; i>=0; i--) sa[--cnt[x[y[i]]]]=y[i];
    }
    void build(char *s,int c_size)
    {
        n=strlen(s);
        m=c_size;
        x=a1;
        y=a2;
        for(int i=0; i<n; i++) x[i]=s[i],y[i]=i;
        x[n]=y[n]=-1;
        sort();
        for(int k=1; k<=n; k<<=1)
        {
            int p=0;
            for(int i=n-k; i<n; i++) y[p++]=i;
            for(int i=0; i<n; i++) if(sa[i]>=k) y[p++]=sa[i]-k;
            sort();
            p=0;
            std::swap(x,y);
            x[sa[0]]=0;
            for(int i=1; i<n; i++)
            {
                if(y[sa[i]]!=y[sa[i-1]]||y[sa[i]+k]!=y[sa[i-1]+k]) p++;
                x[sa[i]]=p;
            }
            if(p+1>=n) break;
            m=p+1;
        }
        for(int i=0; i<n; i++) rank[sa[i]]=i;
        height[0]=0;
        int k=0;
        for(int i=0; i<n; i++)
        {
            if(k) k--;
            if(rank[i]==0) continue;
            int j=sa[rank[i]-1];
            while(i+k<n&&j+k<n&&s[i+k]==s[j+k]) k++;
            height[rank[i]]=k;
        }
    }
} SA;


int main()
{
    char s[N]= {0};
    long long len;
    scanf("%d %s",&len,s);

    SA.build(s,256);

    long long ans=len*(len+1)/2;
        
    for(int i=1; i<len; i++)
    {
        ans-=SA.height[i];
    }

    printf("%lld
",ans);//
    return 0;
}

View Code