洛谷P2408 不同子串个数后缀数组 + Height数组

## 题目描述：

给你一个长为 $N$ $(N<=10^5)$ 的字符串，求不同的子串的个数
我们定义两个子串不同，当且仅当有这两个子串长度不一样或者长度一样且有任意一位不一样。子串的定义：原字符串中连续的一段字符组成的字符串

很妙的一道题，考察了对 $Height$ 数组的理解。

$1.$首先，不难发现任意子串都可以被字符串中后缀串的前缀表达出来

$2.$我们知道， $Height[i]$ 被定义为排名为 $i$ 的后缀串与排名为 $i-1$ 的后缀串的 $LCP$.

而与排名为 $i$ 得后缀串 $LCP$ 值最大的字符串必定是排名为 $i-1$ 的后缀串，他们的 $LCP$

值恰好就是 $Height$ 数组的值，即$Height[i]$.

考虑向后缀串集合中新加入一个后缀串 $sa[k]$, 共会产生 $n-sa[k]+1$ 个前缀串，但是有一些

前缀串在先前就已经会被计算到，会被计算到的前缀部分的最大值是 $Height[k]$，直接减去

$Height[k]$ 即可. 即贡献为 $n-sa[k]+1-Height[k]$.

Code:

#include <cstdio>

#include <algorithm>

#include <cstring>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 1000000

using namespace std;

char str[maxn];

int tr[maxn],rk[maxn],sa[maxn],arr[maxn],c[maxn],height[maxn];

int n,m;

struct Suffix_Array

{

    void qsort()

    {

        for(int i=0;i<=m;++i) c[i]=0;

        for(int i=1;i<=n;++i) ++c[rk[tr[i]]];

        for(int i=1;i<=m;++i) c[i]+=c[i-1];

        for(int i=n;i>=1;--i) sa[c[rk[tr[i]]]--]=tr[i];

    }

    void build()

    {

        for(int i=1;i<=n;++i) rk[i]=arr[i],tr[i]=i;

        qsort();

        for(int k=1;k<=n;k<<=1)

        {

            int num=0;

            for(int i=n-k+1;i<=n;++i) tr[++num]=i;

            for(int i=1;i<=n;++i) if(sa[i]>k) tr[++num]=sa[i]-k;

            qsort();

            swap(rk,tr);

            rk[sa[1]]=1;

            num=1;

            for(int i=2;i<=n;++i)

                rk[sa[i]]=(tr[sa[i]]==tr[sa[i-1]]&&tr[sa[i]+k]==tr[sa[i-1]+k])?num:++num;

            if(num>=n) break;

            m=num;

        }

    }

    void get_height()

    {

        int k=0;

        for(int i=1;i<=n;++i) rk[sa[i]]=i;

        for(int i=1;i<=n;++i){

            if(k) --k;

            int j=sa[rk[i]-1];

            while(arr[i+k]==arr[j+k]) ++k;

            height[rk[i]]=k;

        }

    }

}T;

int main()

{

    //setIO("input");

    scanf("%d",&n);

    scanf("%s",str),m=120;

    for(int i=1;i<=n;++i) arr[i]=str[i-1]-'0';

    T.build();

    T.get_height();

    long long ans=0;

    for(int i=1;i<=n;++i)

        ans+=(long long) (n-sa[i]+1-height[i]);

    printf("%lld",ans);

    return 0;

}

巴特西

洛谷P2408 不同子串个数后缀数组 + Height数组

最新文章

热门文章

巴特西

洛谷P2408 不同子串个数 后缀数组 + Height数组

最新文章

热门文章

洛谷P2408 不同子串个数后缀数组 + Height数组