Description
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 <= 1000
For each test case output one number saying the number of distinct substrings.
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.
題意：給定一個(gè)字符串，求不相同的子串。
思路：每個(gè)子串一定是某個(gè)后綴的前綴，那么原問(wèn)題等價(jià)于求所有后綴之間的不相同的前綴的個(gè)數(shù)。如果所有的后綴按照 suffix(sa[1]), suffix(sa[2]),
suffix(sa[3]), …… ,suffix(sa[n])的順序計(jì)算，不難發(fā)現(xiàn)，對(duì)于每一次新加
進(jìn)來(lái)的后綴 suffix(sa[k]),它將產(chǎn)生 n-sa[k]個(gè)新的前綴。但是其中有height[k]個(gè)是和前面的字符串的前綴是相同的。所以 suffix(sa[k])將“貢獻(xiàn)”
出 n-sa[k]-height[k]個(gè)不同的子串。累加后便是原問(wèn)題的答案。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1010;
int sa[maxn]; //SA數(shù)組，表示將S的n個(gè)后綴從小到大排序后把排好序的
//的后綴的開(kāi)頭位置順次放入SA中
int t1[maxn], t2[maxn], c[maxn];
int rank[maxn], height[maxn];
int s[maxn];
char str[maxn];
void build_sa(int s[], int n, int m) {
int i, j, p, *x = t1, *y = t2;
for (i = 0; i < m; i++) c[i] = 0;
for (i = 0; i < n; i++) c[x[i] = s[i]]++;
for (i = 1; i < m; i++) c[i] += c[i-1];
for (i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
for (j = 1; j <= n; j <<= 1) {
p = 0;
for (i = n-j; i < n; i++) y[p++] = i;
for (i = 0; i < n; i++)
if (sa[i] >= j)
y[p++] = sa[i] - j;
for (i = 0; i < m; i++) c[i] = 0;
for (i = 0; i < n; i++) c[x[y[i]]]++;
for (i = 1; i < m; i++) c[i] += c[i-1];
for (i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1, x[sa[0]] = 0;
for (i = 1; i < n; i++)
x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+j] == y[sa[i]+j] ? p-1 : p++;
if (p >= n) break;
m = p;
}
}
void getHeight(int s[],int n) {
int i, j, k = 0;
for (i = 0; i <= n; i++)
rank[sa[i]] = i;
for (i = 0; i < n; i++) {
if (k) k--;
j = sa[rank[i]-1];
while (s[i+k] == s[j+k]) k++;
height[rank[i]]=k;
}
}
int check(int n, int k, int mid) {
int num = 1;
for (int i = 2; i <= n; i++) {
if (height[i] >= mid) {
num++;
if (num >= k) return 1;
}
else num = 1;
}
return 0;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%s", str);
int n = strlen(str);
for (int i = 0; i <= n; i++)
s[i] = str[i];
build_sa(s, n+1, 128);
getHeight(s, n);
int ans = 0;
for (int i = 1; i <= n; i++)
ans += n - sa[i] - height[i];
printf("%d
", ans);
}
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
