Rockdu's Blog

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 <= 1000

Output

For each test case output one number saying the number of distinct substrings.

Example

Sample Input:
2
CCCCC
ABABA

Sample Output:
5
9

Explanation for the testcase with string ABABA:
len=1 : A,B
len=2 : AB,BA
len=3 : ABA,BAB
len=4 : ABAB,BABA
len=5 : ABABA
Thus, total number of distinct substrings is 9.

题目大概意思就是求一个字符串所有本质不同子串的个数。

考虑到字符串上的统计，我们可以用后缀数组。因为求本质不同的子串很难，我们可以从反面考虑。因为已知所有子串个数为n * (n + 1) / 2个，只需要求重复过的子串个数，相减即为答案。然而这个重复过的子串个数不就是所有Height的和吗！至此，整个题目思路清晰了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define Down(i, a, b) for(register int i = a; i >= b; --i)
using namespace std;
const int maxn = 5e5 + 5;
int a[maxn], SA[maxn], LR[maxn], RK[maxn], tmp[maxn], Height[maxn], n, m;
char s[maxn];

void Rsort(int * ORD) {
	For(i, 0, m) tmp[i] = 0;
	For(i, 1, n) ++tmp[RK[ORD[i]]];
	For(i, 1, m) tmp[i] += tmp[i - 1];
	Down(i, n, 1) SA[tmp[RK[ORD[i]]]--] = ORD[i];
}

bool cmp(int x, int y, int w) {
	return LR[x] == LR[y] && LR[x + w] == LR[y + w];
}

void SA_Create() {
	For(i, 1, n) RK[i] = a[i], LR[i] = i; // 一个字符的情况初始化 
	m = 127, Rsort(LR);
	for(register int w = 1, p = 1; p < n; w += w, m = p) {
		p = 0;
		For(i, n - w + 1, n) LR[++p] = i;
		For(i, 1, n) if(SA[i] > w) LR[++p] = SA[i] - w;
		Rsort(LR), swap(LR, RK), RK[SA[1]] = p = 1;
		For(i, 2, n) RK[SA[i]] = cmp(SA[i], SA[i - 1], w) ? p : ++p;
	}
	int j, k = 0;
	for(register int i = 1; i <= n; Height[SA[i++]] = k)
		for(k = k ? k - 1 : k, j = SA[RK[i] - 1]; a[i + k] == a[j + k]; ++k);
}

int t;

int main() {
	scanf("%d", &t);
	while(t--) {
		memset(a, 0, sizeof(a));
		scanf("%s", s);
		n = strlen(s);
		For(i, 1, n) a[i] = s[i - 1];
		SA_Create();
		long long ans = 0;
		For(i, 1, n) ans += Height[i];
		printf("%lld\n", 1LL * n * (n + 1) / 2 - ans);
	}
	return 0;
}