SPOJ705不同的子串

本文主要是介绍SPOJ705不同的子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目描述】

给定一个字符串，计算其不同的子串个数。

【输入格式】

一行一个仅包含大写字母的字符串，长度<=50000

【输出格式】

一行一个正整数，即不同的子串个数。

【样例输入】

ABABA

【样例输出】

9

可以用后缀数组求出每个后缀的height，然后由于height为当前后缀与前边后缀最长公共前缀的最小值，所以当前后缀的不同子串数为该后缀长度减去该后缀的heght，最后求和即可

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=50000+100;
char s[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn];
inline int idx(char c){return c-'A';
}
inline void build_sa(int n,int m){int *x=t,*y=t2;for(int i=0;i<m;i++)c[i]=0;for(int i=0;i<n;i++)c[x[i]=idx(s[i])]++;for(int i=1;i<m;i++)c[i]+=c[i-1];for(int i=n-1;i>=0;i--)sa[--c[x[i]]]=i;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;for(int i=0;i<m;i++)c[i]=0;for(int i=0;i<n;i++)c[x[y[i]]]++;for(int i=1;i<m;i++)c[i]+=c[i-1];for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];swap(x,y);p=1;x[sa[0]]=0;for(int i=1;i<n;i++){x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k])?p-1:p++;}if(p>=n)break;m=p;}
}
int rank[maxn],height[maxn];
inline void getheight(int n){int h=0;for(int i=0;i<n;i++)rank[sa[i]]=i;for(int i=0;i<n;i++){if(rank[i]==0) h=0;else{int k=sa[rank[i]-1];if(--h<0) h=0;while(s[i+h]==s[k+h]) h++;}height[rank[i]]=h;}
}
int main(){freopen("subst1.in","r",stdin);freopen("subst1.out","w",stdout);scanf("%s",s);int n=strlen(s);s[n]='A'+29;build_sa(n+1,30);getheight(n);long long ans=0;for(int i=0;i<n;i++)ans+=n-sa[i]-height[i];printf("%lld\n",ans);
return 0;
}

这篇关于SPOJ705不同的子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---