SPOJ New Distinct Substrings

https://www.spoj.pl/problems/SUBST1/
这是经典的题目了。。求出后缀数组和Height数组,然后用n*(n+1)/2-所有Height的和就OK了囧。。。
Code:
#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();
}

13 thoughts on “SPOJ New Distinct Substrings

Leave a Reply to WalterKix Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>