验证中...
语言: C/C++
分类: 其他
最后更新于 2018-08-11 11:09
【BZOJ3238】【AHOI2013】差异
原始数据 复制代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500010;
int c[N],sa[N],rk[N],ht[N],y[N],x[N];
char s[N];
int n,m;
void get_sa(){
for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
for(int i=2;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i;i--) sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int p=0;
for(int i=n-k+1;i<=n;i++) y[++p]=i;
for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;
for(int i=1;i<=m;i++) c[i]=0;
for(int i=1;i<=n;i++) c[x[i]]++;
for(int i=2;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i;i--) sa[c[x[y[i]]]--]=y[i];
swap(x,y);
x[sa[1]]=1,p=1;
for(int i=2;i<=n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
if(n==p) break;
m=p;
}
int k=0;
for(int i=1;i<=n;i++) rk[sa[i]]=i;
for(int i=1;i<=n;i++){
if(k) k--;
if(rk[i]==1) continue;
int j=sa[rk[i]-1];
while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) k++;
ht[rk[i]]=k;
}
}
int lpos[N],rpos[N];
int st[N],top;
int main(){
scanf("%s",s+1);
n=strlen(s+1);
m=122;
get_sa();
st[top]=0;
for(int i=1;i<=n;i++){
while(top&&ht[st[top]]>ht[i]) top--;
lpos[i]=st[top];
st[++top]=i;
}
top=0;
st[top]=n+1;
for(int i=n;i;i--){
while(top&&ht[st[top]]>=ht[i]) top--;
rpos[i]=st[top];
st[++top]=i;
}
ll ans=0;
for(int i=1;i<=n;i++) ans-=(ll)(i-lpos[i])*(rpos[i]-i)*ht[i];
printf("%lld",ans*2+(ll)(n-1)*n*(n+1)/2);
return 0;
}

评论列表( 0 )

你可以在登录后,发表评论

搜索帮助