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
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.

(Tjandra Satria Gunawan)(曾毅昆): 2015-01-02 22:42:54

Here is my summary:
O(n*log^2(n)) --> definitely TLE even pointer opti used.
O(n*log(n)) --> longer code, AC
O(n) --> there're exist algorithm with this amortized complexity but very painful to code. I'm sure I this O(n) can get AC in 0.00s

Gaurav Babbar: 2014-10-23 21:11:03

SAM is givig TLE! what is the size of the input alphabet set??
----
AC after optimisatons :)

Last edit: 2014-10-24 21:15:36
Varun Gambhir: 2014-10-23 18:59:07

n*logn*logn algorithm for building suffix array gives tle :(


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