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
jahid_hasan17:
2020-10-12 18:34:34
it can be done using suffix array(nlogn),suffix automaton(n) |
|
avsd_47:
2020-08-10 09:34:16
use fast i/o if u r facing issue in cpp |
|
anish1712:
2020-06-21 16:59:27
Can someone let me know when I use total number of substrings as (n+1)*n/2 it fails but when I use summation of
|
|
yuhta:
2018-10-31 17:09:12
Test is weak. Got 0.05 using naive sort (n^2*log(n)). |
|
karan_yadav:
2018-07-20 06:30:06
Suffix array using Radix sort will get you through 0.01s |
|
prince_batra:
2018-02-09 12:43:04
Can string also contain lowercase char. ? |
|
seyedssz:
2017-08-24 14:04:32
0.02 s with O(n*log^2) |
|
tnorris:
2017-07-01 02:49:24
Naive Solution is O(n^2 * logn) - hits time limit
|
|
jaijoshi:
2017-04-29 21:39:52
I am using n*logn*logn solution with array of structure for buiding suffix array and still getting TLE. and for lcp i am using kasai's algo. Please help me.
|
|
sultania23:
2017-03-26 12:05:39
n*logn*logn AC |
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 |