시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 4 | 3 | 3 | 100.000% |
How many distinct substrings does a given string $S$ have?
For example, if $S =$ abc
, $S$ has $7$ distinct substrings: , a
, b
, c
, ab
, bc
, abc
. Note that the empty string and $S$ itself are considered substrings of $S$.
On the other hand, if $S =$ aaa
. $S$ has only $4$ distinct substrings: , a
, aa
, aaa
.
The first line of the input file contains $N$, the number of test cases. For each test case, a line follows giving $S$, a string of from $1$ to $5000$ alphanumeric characters.
Your output consists of one line per case, giving the number of distinct substrings of $S$.
50% of test cases will have $l$ (the length of the string) where $l \le 1000$. For all cases, $l \le 5000$.
2 abc aaa
7 4