题解 P2408 【不同子串个数】

珅肐 · 2019-03-29 08:36:22 · 题解

统计一个串不同的子串个数：

我们可以利用LCP来做，

根据定义，后缀suf(i)和它的前一名后缀suf(k)最长公共前缀是Height[i]，

这两个串的前缀，就是原字符串的子串，

那么这两个串产生的相同的子串，数目就是Height[rak[i]]。

所有后缀产生的前缀，相同的个数是\sum ^n_1 Height[rak[i]]

一个长度为n的字符串，产生的子串个数是\frac {n(n+1)}2个，

最后答案为总个数减去相同的个数，即:

完整代码奉上：

#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<cstring>
#include<queue>
using namespace std;
inline int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch))f|=ch=='-',ch=getchar();
    while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}
char s[100007];
int N,M;
int rak[100007],sa[100007],tp[100007],tax[100007];
inline void bucket(){
    for(int i=0;i<=M;++i)tax[i]=0;
    for(int i=1;i<=N;++i)tax[rak[i]]++;
    for(int i=1;i<=M;++i)tax[i]+=tax[i-1];
    for(int i=N;i>=1;--i)sa[tax[rak[tp[i]]]--]=tp[i];
}
inline void suffix_sort(){//SA模板
    M=128;
    for(int i=1;i<=N;++i)rak[i]=s[i]-'a'+1,tp[i]=i;
    bucket();
    for(int w=1,p=0;p<N;M=p,w<<=1){
        p=0;
        for(int i=1;i<=w;++i)tp[++p]=N-w+i;
        for(int i=1;i<=N;++i)if(sa[i]>w)tp[++p]=sa[i]-w;
        bucket();
        swap(tp,rak);
        rak[sa[1]]=p=1;
        for(int i=2;i<=N;++i)
            rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]] && tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
    }
}
int height[100007];
inline void Get_Height(){//求Height数组
    int k=0;
    for(int i=1;i<=N;++i){
        if(k)k--;
        int j=sa[rak[i]-1];
        while(s[i+k]==s[j+k])++k;
        height[rak[i]]=k;
    }
}
int main(){
    N=read();scanf("%s",s+1);
    suffix_sort();
    Get_Height();
    long long ans=1ll*N*(N+1)/2;//总子串个数
    for(int i=1;i<=N;++i)ans-=height[rak[i]];//减去相同的个数
    printf("%lld\n",ans);
    return 0;//好习惯..
}