https:\/\/www.spoj.pl\/problems\/SUBST1\/
\u8fd9\u662f\u7ecf\u5178\u7684\u9898\u76ee\u4e86\u3002\u3002\u6c42\u51fa\u540e\u7f00\u6570\u7ec4\u548cHeight\u6570\u7ec4\uff0c\u7136\u540e\u7528n*(n+1)\/2-\u6240\u6709Height\u7684\u548c\u5c31OK\u4e86\u56e7\u3002\u3002\u3002
Code\uff1a
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>1,maxn=50000+10;
using namespace std;
char C[maxn];int ta[maxn],tb[maxn],sa[maxn],n,m,*x=ta,*y=tb,h[maxn];
void Sort()
{
static int w[maxn];
rep(i,m)w[i]=0;rep(i,n)w[x[y[i]]]++;rep(i,m-1)w[i+1]+=w[i];
for(int i=n-1;i>=0;i–)sa[–w[x[y[i]]]]=y[i];
}
bool cmp(int a,int b,int l)
{return y[a]==y[b]&&y[a+l]==y[b+l];}
void Da()
{
rep(i,n)x[i]=C[i],y[i]=i;Sort();int i,j,p;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++)y[p++]=i;
rep(i,n)if(sa[i]>=j)y[p++]=sa[i]-j;Sort();
for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(sa[i-1],sa[i],j)?p-1:p++;
}
}
void CalH()
{
static int R[maxn];
int i,j,k=0;
for(i=1;i<=n;i++)R[sa[i]]=i;
for(i=0;i<n;h[R[i++]]=k)
for(k?k–:0,j=sa[R[i]-1];C[i+k]==C[j+k];k++);
}
void Solve()
{
scanf("%s",C);n=strlen(C);C[n++]=0;m=256;
Da();n–;long long ans=n;ans*=n+1;ans\/=2;
CalH();rep(i,n)ans-=h[i+1];cout<<ans<<endl;
}
int main()
{
\/\/freopen("in","r",stdin);
int t;cin>>t;while(t–)Solve();
} <\/p>\n","protected":false},"excerpt":{"rendered":"
https:\/\/www.spoj.pl\/problems\/SUBST1\/\u8fd9\u662f\u7ecf\u5178\u7684\u9898\u76ee\u4e86\u3002\u3002\u6c42\u51fa\u540e\u7f00\u6570\u7ec4\u548cHeight\u6570\u7ec4\uff0c\u7136\u540e\u7528n*(n+1)\/2-\u6240\u6709Height\u7684\u548c\u5c31OK\u4e86\u56e7\u3002\u3002\u3002Code\uff1a#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#include <cstring>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backconst int inf=~0U>>1,maxn=50000+10;using namespace std;char C[maxn];int ta[maxn],tb[maxn],sa[maxn],n,m,*x=ta,*y=tb,h[maxn];void Sort(){ static int w[maxn]; rep(i,m)w[i]=0;rep(i,n)w[x[y[i]]]++;rep(i,m-1)w[i+1]+=w[i]; for(int i=n-1;i>=0;i–)sa[–w[x[y[i]]]]=y[i];}bool cmp(int a,int b,int l){return y[a]==y[b]&&y[a+l]==y[b+l];}void Da(){ rep(i,n)x[i]=C[i],y[i]=i;Sort();int i,j,p; for(j=1,p=1;p<n;j*=2,m=p) { for(p=0,i=n-j;i<n;i++)y[p++]=i; rep(i,n)if(sa[i]>=j)y[p++]=sa[i]-j;Sort(); for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++) x[sa[i]]=cmp(sa[i-1],sa[i],j)?p-1:p++; }}void CalH(){ static int R[maxn]; int i,j,k=0; for(i=1;i<=n;i++)R[sa[i]]=i; for(i=0;i<n;h[R[i++]]=k) for(k?k–:0,j=sa[R[i]-1];C[i+k]==C[j+k];k++);}void Solve(){ scanf("%s",C);n=strlen(C);C[n++]=0;m=256; Da();n–;long long […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/241"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=241"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/241\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=241"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=241"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=241"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}