a167: SPOJ 694. Distinct Substrings
Tags : SA Suffix tree
Accepted rate : 32人/37人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-06-21 22:51

Content

Given a string, we need to find the total number of its distinct substrings.

給一個字串,我們需要找到不同子字串的總數

Input

T- number of test cases. T<=50;
Each test case consists of one string, whose length is <= 5000

第一行會有一個整數T,代表接下來會有幾筆測資 T ≦ 50

接下來每組的測試字串長度 L ≦ 5000

Output
For each test case output one number saying the number of distinct substrings.
Sample Input #1
2
CCCCC
ABABA
Sample Output #1
5
9
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
Hint :

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

 

 

 

 

×數據範圍稍作修改

Tags:
SA Suffix tree
出處:
SPOJ 694 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」