Given a string, we need to find the total number of its distinct substrings.
Input
T- number of test cases. T<=20; Each test case consists of one string, whose length is <= 50000
Output
For each test case output one number saying the number of distinct substrings.
Example
Input: 2 CCCCC ABABA Output: 5 9
题目大意：给一个字符串，问这个字符串中不同的子串一共有多少个。
思路：构建后缀数组。如样例ABABA的5个后缀排序后分别为：
A
ABA
ABABA
BA
BABA
我们可以看作所有后缀的所有前缀构成所有的子串。
从上面可以看出，在A中，A第一次出现。在ABA中，AB和ABA第一次出现。在ABABA中，ABAB和ABABA第一次出现。
那么容易看出，对于一个suffix(sa[i])，其中有height[i]个子串是和前一个重复了的。其他都没有和前一个重复，而且他们都不会和之前所有的子串重复（因为如果前面有和suffix(sa[i])的前缀子串重复的次数比suffix(sa[i-1])要多的话，它应该在suffix(sa[i])和suffix(sa[i-1])之间，这显然不符合后缀数组的性质）
所以求出height[]数组后，总的子串数为n*(n+1)/2，那么答案就为n*(n+1)/2 - sum{height[]}
代码（705:0.75S）
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 typedef long long LL; 7 8 const int MAXN = 50010; 9 10 int sa[MAXN], c[MAXN], rank[MAXN], height[MAXN], tmp[MAXN]; 11 char s[MAXN]; 12 int T, n; 13 14 void makesa(int m) { 15 memset(c, 0, m * sizeof(int)); 16 for(int i = 0; i < n; ++i) ++c[rank[i] = s[i]]; 17 for(int i = 1; i < m; ++i) c[i] += c[i - 1]; 18 for(int i = 0; i < n; ++i) sa[--c[rank[i]]] = i; 19 for(int k = 1; k < n; k <<= 1) { 20 for(int i = 0; i < n; ++i) { 21 int j = sa[i] - k; 22 if(j < 0) j += n; 23 tmp[c[rank[j]]++] = j; 24 } 25 int j = c[0] = sa[tmp[0]] = 0; 26 for(int i = 1; i < n; ++i) { 27 if(rank[tmp[i]] != rank[tmp[i - 1]] || rank[tmp[i] + k] != rank[tmp[i - 1] + k]) 28 c[++j] = i; 29 sa[tmp[i]] = j; 30 } 31 memcpy(rank, sa, n * sizeof(int)); 32 memcpy(sa, tmp, n * sizeof(int)); 33 } 34 } 35 36 void calheight() { 37 for(int i = 0, k = 0; i < n; height[rank[i++]] = k) { 38 if(k > 0) --k; 39 int j = sa[rank[i] - 1]; 40 while(s[i + k] == s[j + k]) ++k; 41 } 42 } 43 44 LL solve() { 45 LL ret = LL(n) * (n - 1) / 2; 46 for(int i = 1; i < n; ++i) ret -= height[i]; 47 return ret; 48 } 49 50 int main() { 51 scanf("%d", &T); 52 while(T--) { 53 scanf("%s", s); 54 n = strlen(s) + 1; 55 makesa(128); 56 calheight(); 57 printf("%lld\n", solve()); 58 } 59 }
SPOJ 694 Distinct Substrings/SPOJ 705 New Distinct Substrings（后缀数组）