SUBST1 - New Distinct Substrings


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

Input

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

Output

For each test case output one number saying the number of distinct substrings.

Example

Input:
2
CCCCC
ABABA

Output:
5
9

hide comments
eightnoteight: 2015-06-11 19:29:20

O(n*log^2(n)) with out using IO optimization got AC..

Martin Radev: 2015-06-10 10:07:03

Note that the symbols in the input are not only in A...Z.
Suffix tree is fast enough using McCreight's construction algorithm.

Manoj Kumar Regar: 2015-05-25 16:02:44

oh gosh! n^2 logn ... naive solution got accepted in 0.06.....

superfloyd: 2015-05-18 10:04:04

for this problem could you use tries?

Crazyxx: 2015-05-04 08:37:35

SAM 0.08s & 42M XD

Sourabh Bansal: 2015-04-20 08:09:17

Suffix Array O(n lg^2(n)) AC .... 0.07 s :)

mkrjn99: 2015-02-03 06:54:35

nlog^2(n): TLE
nlogn: AC

Rishit Sanmukhani: 2015-02-01 12:30:10

Got AC :) Nice question.
n(logn)^2 doesn't pass. We have to make it nlogn. Used counting sort.

Anmol Pandey: 2015-01-17 17:51:46

O(n*log(n)^2) is AC.

Rodrigo Horruitiner: 2015-01-06 00:13:36

Actually, the O(n) construction isn't much faster than the O(n*logn*logn) one, if at all. The skew algorithm has big constants because of the recursion and the radix sort. Just optimize your code.


Added by:Hoang Hong Quan
Date:2006-01-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Base on a problem in ByteCode06