题目:http://cojs.tk/cogs/problem/problem.php?pid=1709
1709. [SPOJ705]不同的子串
★★ 输入文件:subst1.in
输出文件:subst1.out
简单对比
时间限制:1 s 内存限制:256 MB
【题目描述】
给定一个字符串,计算其不同的子串个数。
【输入格式】
一行一个仅包含大写字母的字符串,长度<=50000
【输出格式】
一行一个正整数,即不同的子串个数。
【样例输入】
ABABA
【样例输出】
9
【来源】
SPOJ 705 New Distinct Substrings
自动选择评测机
打开 O2 优化
COGS Grader
无优化开关
提交代码 Pascal C C++
题解:
后缀数组
我们可以想到ans=总共子串的个数-相同的个数。
相同的个数即为height[]之和。
(len为字符串长度)总共子串的个数:
长度为1的个数:len
长度为2的个数:len-1
.
.
.
所以总共个数为len+(len-1)……+2+1=(len*(len-1))/2
#include<bits/stdc++.h>
using namespace std;
#define MAXN 50010
#define LL long long
int Ws[MAXN],sa[MAXN],wa[MAXN],wb[MAXN],wv[MAXN],Rank[MAXN],height[MAXN];
char str[MAXN];
int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&&(r[a+l]==r[b+l]);}
void DA(char *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=;i<m;i++)Ws[i]=;
for(i=;i<n;i++)Ws[x[i]=r[i]]++;
for(i=;i<m;i++)Ws[i]+=Ws[i-];
for(i=n-;i>=;i--)sa[--Ws[x[i]]]=i;
for(j=,p=;p<n;j*=,m=p)
{
for(p=,i=n-j;i<n;i++)y[p++]=i;
for(i=;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=;i<n;i++)wv[i]=x[y[i]];
for(i=;i<m;i++)Ws[i]=;
for(i=;i<n;i++)Ws[wv[i]]++;
for(i=;i<m;i++)Ws[i]+=Ws[i-];
for(i=n-;i>=;i--)sa[--Ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
}
}
void calheight(int n)
{
int i,j,k=;
for(i=;i<=n;i++)Rank[sa[i]]=i;
for(i=;i<n;height[Rank[i++]]=k)
for(k?k--:,j=sa[Rank[i]-];str[i+k]==str[j+k];k++);
}
int main()
{
freopen("subst1.in","r",stdin);
freopen("subst1.out","w",stdout);
int lstr,i;
LL ans=;
scanf("%s",str);
lstr=strlen(str);
str[lstr+]=;
DA(str,sa,lstr+,);
calheight(lstr);
ans=((LL)(lstr+)*lstr)/;
for(i=;i<=lstr;i++)ans-=(LL)height[i];
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return ;
}