# 某島

… : "…アッカリ～ン . .. . " .. .
September 16, 2010

## SPOJ 705. New Distinct Substrings

### Brief description :

SPOJ 694. 數據加強版，

/*
Author : xiaodao
Prob : SPOJ 705. New Distinct Substrings
Status  : Accepted
Last modify : GMT +8. Sept 16th 11:07
Tags : Suffix Array
*/

#include
#include
#include
#include
using namespace std;

const int INF = 100000;
const int N = 50000, M = 256;
int SA[N], rank[N], height[N], key[N];
string A; int C[N], t1[N+1], t2[N+1];
int n, m; long long ans;

void init(){
int i, j, k, l; int *X = t1, *Y = t2;
cin >> A; n = A.size(); m = M;

memset(C, 0, sizeof(C));
for (i=0;i=0;i--) SA[--C[X[i]]] = i;

X[n] = Y[n] = INF;

for (l=1;l= l) Y[j++] = SA[i] - l;
for (i=0;i=0;i--) SA[--C[key[i]]] = Y[i];

swap(X, Y);
X[SA[0]] = j = 0;
for (i=1;i0) k--;
if (rank[i]==0) height[0] = 0;
else {
j = SA[rank[i] - 1];
while (A[i+k]==A[j+k]) k++;
height[rank[i]] = k;
}
}
}

void solve(){
ans = (long long)(n)*(n+1)/2;
for (int i=1;i> T;
while (T--){
init(); solve();
cout << ans << endl;
}

}