TopCoder

Thumb square output jddoia
$\huge南ことり$
不要再虐我了$ε=ε=ε=ε=ε=ε=┌(; ̄◇ ̄)┘$

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

36.7% (11/30)

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

第一筆範例測試資料:
jizz
infor
wordword
ramen
第二筆範例測試資料:
fortytwo
aaaaaa
lamian
twowok
gordonramsay
第三筆範例測試資料:
xgpuamkxk
zhkbpph
kin
ezplv
jaqmopodot
rjzriml

Sample Output

第一筆範例測試資料的答案:
10
16
27
16
第二筆範例測試資料的答案:
35
7
21
19
76
第三筆範例測試資料的答案:
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 (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