本文共 2292 字，大约阅读时间需要 7 分钟。
题目链接
Given a string, we need to find the total number of its distinct substrings.
T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 50000
For each test case output one number saying the number of distinct substrings.
/* * Author: sweat123 * Created Time: 2016/6/29 13:46:26 * File Name: main.cpp */#include #include #include #include #include #include #include #include #include #include #include #include #define INF 1<<30#define MOD 1000000007#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define pi acos(-1.0)using namespace std;const int MAXN = 50010;char s[MAXN];int wa[MAXN],wb[MAXN],wc[MAXN],n,height[MAXN],r[MAXN],Rank[MAXN],sa[MAXN];void da(int *r,int *sa,int n,int m){ int *x = wa,*y = wb; for(int i = 0; i < m; i++)wc[i] = 0; for(int i = 0; i < n; i++)wc[x[i] = r[i]] ++; for(int i = 0; i < m; i++)wc[i] += wc[i-1]; for(int i = n - 1; i >= 0; i--)sa[--wc[x[i]]] = i; for(int p = 1,k = 1; p < n; m = p,k <<= 1){ p = 0; for(int i = n - k; i < n; i++)y[p++] = i; for(int i = 0; i < n; i++)if(sa[i] >= k)y[p++] = sa[i] - k; for(int i = 0; i < m; i++)wc[i] = 0; for(int i = 0; i < n; i++)wc[x[y[i]]] ++; for(int i = 0; i < m; i++)wc[i] += wc[i-1]; for(int i = n - 1; i >= 0; i--)sa[--wc[x[y[i]]]] = y[i]; swap(x,y); p = 1; x[sa[0]] = 0; for(int i = 1; i < n; i++){ x[sa[i]] = (y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k])?p-1:p++; } } }void calheight(int *r,int *sa,int n){ for(int i = 1; i <= n; i++)Rank[sa[i]] = i; int j,k; k = 0; for(int i = 0; i < n; height[Rank[i++]] = k){ for(k?k--:0,j = sa[Rank[i]-1]; r[j+k] == r[i+k]; k++); } }void solve(){ int ans = 0; for(int i = 1; i <= n; i++){ int tp = height[i]; int len = n - sa[i]; ans += len - tp; } printf("%d\n",ans);}int main(){ int t; scanf("%d",&t); while(t--){ scanf("%s",s); n = strlen(s); for(int i = 0; i < n; i++){ r[i] = s[i]; } r[n] = 0; da(r,sa,n+1,128); calheight(r,sa,n); solve(); } return 0;}
转载于:https://www.cnblogs.com/sweat123/p/5627008.html