题目连接
题意：求所有不同的子串个数。
思路：后缀数组。和上一道题一样，就是数据范围变成了 5E4…1A
代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月02日 星期二 18时32分28秒 4File Name :code/spoj/subst1.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=5E4+7; 32char s[N]; 33int sa[N],rk[N],t[N],t2[N],cnt[N],height[N]; 34int cmp (int *r,int a,int b,int l){ return r[a]==r[b]&&r[a+l]==r[b+l];} 35void getSa(int n,int m) 36{ 37 int *x=t,*y=t2; 38 ms(cnt,0); 39 for ( int i = 0 ; i < n ; i++) cnt[x[i]=s[i]]++; 40 for ( int i = 0 ; i < m ; i++) cnt[i]+=cnt[i-1]; 41 for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[i]]] = i; 42 for ( int k = 1 ; k <= n ; k<<=1) 43 { 44 int p = 0; 45 for ( int i = n-k ; i < n ; i++) y[p++] = i; 46 for ( int i = 0 ; i < n; i++) if (sa[i]>=k) y[p++] = sa[i]-k; 47 ms(cnt,0); 48 for ( int i = 0 ; i <n ; i++) cnt[x[y[i]]]++; 49 for ( int i = 0 ;i < m ; i++) cnt[i]+=cnt[i-1]; 50 for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[y[i]]]] = y[i]; 51 swap(x,y); 52 p = 1; 53 x[sa[0]] = 0; 54 for ( int i = 1 ; i < n ; i++ ) 55 x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++; 56 if (p>=n) break; 57 m = p; 58 } 59} 60void getHeight( int n) 61{ 62 int k = 0 ; 63 for ( int i = 0 ; i <n ; i ++) rk[sa[i]] = i ; 64 height[0] = 0 ; 65 for ( int i = 0 ; i < n ; i++) 66 { 67 if (rk[i]==0) continue; 68 if (k) k--; 69 int j = sa[rk[i]-1]; 70 while (s[i+k]==s[j+k]) k++; 71 height[rk[i]] = k; 72 } 73} 74int getSuffix(char s[]) 75{ 76 int len = strlen(s); 77 int up = 0 ; 78 for ( int i = 0 ; i < len ; i++) 79 { 80 int val = s[i]; 81 up = max(up,val); 82 } 83 s[len++]='$'; 84 getSa(len,up+1); 85 getHeight(len); 86 return len; 87} 88int solve ( int n) 89{ 90 ms(cnt,0); 91 int up = 0; 92 for ( int i = 0 ;i <n ; i ++) cnt[height[i]]++, up = max(up,height[i]); 93 for ( int i = up-1 ; i >= 1; i--) cnt[i]+=cnt[i+1]; 94 int res = 0 ; 95 for ( int i = 1 ; i <=up ; i++) 96 res+=cnt[i]; 97 return res; 98} 99int main() 100{ 101 #ifndef ONLINE_JUDGE 102 freopen("code/in.txt","r",stdin); 103 #endif 104 int T; 105 scanf("%d",&T); 106 while (T--) 107 { 108 scanf("%s",s); 109 int len = getSuffix(s); 110 LL ans = 1LL*len*(len-1)/2; 111 ans-=1LL*solve(len); 112 printf("%lld\n",ans); 113 } 114 #ifndef ONLINE_JUDGE 115 fclose(stdin); 116 #endif 117 return 0; 118}