2178 . 到底有幾個？

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

$nA-NIl$
用心練題，不要跟我一樣600題還那麼爛

User's AC Ratio

100.0% (9/9)

Submission's AC Ratio

41.9% (18/43)

Tags

Description

給你$N$個由小寫字母a-z組成的字串$S_i$，請對於每一個字串計算其到底有幾個相異的子字串。如果一個字串$B$為$A$的子字串，則$B$可以透過$A$刪除頭尾的連續字元所取得。而且，我們特殊定義空字串是任何字串的子字串。保證$N \leq 10^ 5$，且$\sum |S_i| \leq 2 \times 10^ 5$。我們定義兩個字串$A$和$B$不同若且唯若兩個條件中至少滿足一個：

  • $|A| \not = |B|$
  • $\exists i: \;1 \leq i \leq \min(|A|, |B|) \land A_i \not= B_i$

Input Format

請讀檔到EOF。輸入的第$i$行會有一個字串$S_i$。

Output Format

對於每一個字串$S_i$，請輸出一個數字$X_i$，代表$S_i$有幾個相異的子字串。

Sample Input 1

jizz
infor
wordword
ramen

Sample Output 1

10
16
27
16

Sample Input 2

fortytwo
aaaaaa
lamian
twowok
gordonramsay

Sample Output 2

35
7
21
19
76

Sample Input 3

xgpuamkxk
zhkbpph
kin
ezplv
jaqmopodot
rjzriml

Sample Output 3

44
27
7
16
54
28

Hints

Problem Source

by Seanliu

Subtasks

No. Testdata Range Score
1 0~15 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 1
6 1000 262144 262144 1
7 1000 262144 262144 1
8 1000 262144 262144 1
9 1000 262144 262144 1
10 1000 262144 262144 1
11 1000 262144 262144 1
12 1000 262144 262144 1
13 1000 262144 262144 1
14 1000 262144 262144 1
15 1000 262144 262144 1
Submit
Back to Top