| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
|||||||||
|
2015-06-11 19:29:20 eightnoteight
O(n*log^2(n)) with out using IO optimization got AC.. |
|||||||||
|
2015-06-10 10:07:03 Martin Radev
Note that the symbols in the input are not only in A...Z. Suffix tree is fast enough using McCreight's construction algorithm. |
|||||||||
|
2015-05-25 16:02:44 Manoj Kumar Regar
oh gosh! n^2 logn ... naive solution got accepted in 0.06..... |
|||||||||
|
2015-05-18 10:04:04
for this problem could you use tries? |
|||||||||
|
2015-05-04 08:37:35 Crazyxx
SAM 0.08s & 42M XD |
|||||||||
|
2015-04-20 08:09:17 Sourabh Bansal
Suffix Array O(n lg^2(n)) AC .... 0.07 s :) |
|||||||||
|
2015-02-03 06:54:35 mkrjn99
nlog^2(n): TLE nlogn: AC |
|||||||||
|
2015-02-01 12:30:10 Rishit Sanmukhani
Got AC :) Nice question. n(logn)^2 doesn't pass. We have to make it nlogn. Used counting sort. |
|||||||||
|
2015-01-17 17:51:46 Anmol Pandey
O(n*log(n)^2) is AC. |
|||||||||
|
2015-01-06 00:13:36 Rodrigo Horruitiner
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. |
|||||||||
RSS