2011-06-23 07:33:05Morris
a167. SPOJ 694. Distinct Substrings
a167. SPOJ 694. Distinct Substrings
內容 :
Given a string, we need to find the total number of its distinct substrings.
給一個字串,我們需要找到不同子字串的總數
輸入說明
:
T- number of test cases. T<=50;
Each test case consists of one string, whose length is <= 5000
第一行會有一個整數T,代表接下來會有幾筆測資 T ≦ 50
接下來每組的測試字串長度 L ≦ 5000
輸出說明
:
For each test case output one number saying the number of distinct substrings.
範例輸入 :
2 CCCCC ABABA
範例輸出 :
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.
Added by: | Prasanna |
Date: | 2006-01-13 |
Time limit: | 1s |
Source limit: | 50000B |
Languages: | All except: PERL 6 |
Resource: | ByteCode '06 |
×數據範圍稍作修改
出處
:
SPOJ 694 | SA | Suffix tree | others
(管理:morris1028)
作法 : Suffix array(SA)
把所有後綴做一次排序,然後建出高度數組,通常是用height[]
我下面就打LCAP[],晚點再做修改,
例如 : ABABA
字串有 ABABA,BABA,ABA,BA,A
排序完
A
ABA
ABABA
BA
BABA
高度數組,就是跟排序完後,有幾個跟他相同的前綴(也就是前幾個相同)
得到
A => 0
ABA => 1
ABABA => 3 (ABA同,故=3)
BA => 0
BABA =>2 (BA同,故=2)
排序的部份,我好像沒有出極限測資,用普通的字串排序似乎也行哦
然後答案就是每個後綴的長度 減去 高度數組的大小 的總和
這個部份,請自行思考,簡單的說,就是減去重複的部份
A : 1 - 0 = 1
ABA : 3 - 1 = 2 (從頭開始,只會有AB、ABA 2 組)
ABABA : 5 - 3 = 2 (從頭開始,ABAB、ABABA 2 組)
BA : 2 - 0 = 2 (從頭開始,B、BA)
BABA : 4 - 2 = 2 (從頭開始 BAB、BABA)
Ans = 1+2+2+2+2 = 9
作法 : Suffix array(SA)
把所有後綴做一次排序,然後建出高度數組,通常是用height[]
我下面就打LCAP[],晚點再做修改,
例如 : ABABA
字串有 ABABA,BABA,ABA,BA,A
排序完
A
ABA
ABABA
BA
BABA
高度數組,就是跟排序完後,有幾個跟他相同的前綴(也就是前幾個相同)
得到
A => 0
ABA => 1
ABABA => 3 (ABA同,故=3)
BA => 0
BABA =>2 (BA同,故=2)
排序的部份,我好像沒有出極限測資,用普通的字串排序似乎也行哦
然後答案就是每個後綴的長度 減去 高度數組的大小 的總和
這個部份,請自行思考,簡單的說,就是減去重複的部份
A : 1 - 0 = 1
ABA : 3 - 1 = 2 (從頭開始,只會有AB、ABA 2 組)
ABABA : 5 - 3 = 2 (從頭開始,ABAB、ABABA 2 組)
BA : 2 - 0 = 2 (從頭開始,B、BA)
BABA : 4 - 2 = 2 (從頭開始 BAB、BABA)
Ans = 1+2+2+2+2 = 9
/**********************************************************************************/
/* Problem: a167 "SPOJ 694. Distinct Substrings" from SPOJ 694 | SA | Suffix tree | others*/
/* Language: C */
/* Result: AC (68ms, 434KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-21 22:46:38 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
#define MaxL 5002
void Merge(int, int, int);
void MergeSort(int, int);
struct xy_change_rank{
int index, v;
}Data[MaxL], X[MaxL];
char S[MaxL], base_rank[256];
int s2[20]={1}, rank[MaxL], SA[MaxL], L;
int LCAP_Build(int);
void MergeSort(int l, int h) {
if(l < h) {
int m=(l+h)/2;
MergeSort(l ,m);
MergeSort(m+1,h);
Merge(l,m,h);
}
}
void Merge(int l, int m, int h) {
int In1 = l, In2 = m+1;
int a, b, Top = 0;
while(In1 <= m && In2 <= h)
if(Data[In1].v <= Data[In2].v)
X[Top++] = Data[In1++];
else X[Top++] = Data[In2++];
while(In1 <= m) X[Top++] = Data[In1++];
while(In2 <= h) X[Top++] = Data[In2++];
for(a = 0, b = l; a < Top; a++, b++)
Data[b] = X[a];
}
void Doubling_Algorithm() {
int a, b, C, temp;
L=strlen(S);
int Queue[MaxL] = {-1};
char Mask[MaxL];
for(a = 0; a < L; a++)
rank[a] = base_rank[S[a]], Mask[a] = 0,
Data[a].v = rank[a], Data[a].index = a;
MergeSort(0, L-1);
for(a = 0; s2[a] < L; a++) {
temp = Data[0].v, C = 1;
for(b = 0; b < L; b++) {
if(Data[b].v != temp || Mask[b] == 1)
Queue[C] = b-1, temp = Data[b].v, C++, Mask[b] = 1;
rank[Data[b].index] = C;
}
Queue[C] = L-1, C++;
for(b = 0; b < L; b++) {
if(Data[b].index + s2[a]<L) Data[b].v = rank[Data[b].index + s2[a]];
else Data[b].v = 0;
}
for(b = 1; b < C; b++)
MergeSort(Queue[b-1]+1, Queue[b]);
}
for(a = 0; a < L; a++)
SA[a] = Data[a].index;
LCAP_Build(L);
}
int LCAP[MaxL];
int LCAP_Build(int L) {
int a, b, k = 0;
for(a = 0; a < L; a++) rank[SA[a]] = a;
for(a = 0; a < L; a++) {
if(rank[a] == 0) {LCAP[rank[a]] = 0; continue;}
if(a == 0 || LCAP[rank[a-1]] <= 1) k = 0;
else k = LCAP[rank[a-1]] - 1;
while(S[SA[rank[a]-1]+k] == S[SA[rank[a]]+k]) k++;
LCAP[rank[a]] = k;
}
}
main() {
int a, T;
for(a = 1; a < 20; a++) s2[a] = s2[a-1]*2;
for(a = 32; a <= 126; a++) base_rank[a] = a;
scanf("%d", &T);
while(T--) {
scanf("%s", S);
Doubling_Algorithm();
int Ans = 0, L = strlen(S);
for(a = 0; a < L; a++) {
Ans += (L-a)-LCAP[a];
}
printf("%d\n", Ans);
}
return 0;
}