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組成的字串Si，請對於每一個字串計算其到底有幾個相異的子字串。如果一個字串B為A的子字串，則B可以透過A刪除頭尾的連續字元所取得。而且，我們特殊定義空字串是任何字串的子字串。保證N≤105，且∑|Si|≤2×105。我們定義兩個字串A和B不同若且唯若兩個條件中至少滿足一個：

  • |A|≠|B|
  • ∃i:1≤i≤min(|A|,|B|)∧Ai≠Bi

Input Format

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

Output Format

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

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