| 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
|
|||||||||
|
2017-03-26 12:04:59
2 days to figure out by taking little help..nice problem |
|||||||||
|
2016-07-16 00:24:06 deerishi
Why does O(nlogn) (suffix array using radix sort) time out ? Last edit: 2016-07-16 00:24:19 |
|||||||||
|
2016-03-22 16:36:41 ravi
nlognlogn =tle nlogn=ac better to learn nlogn found this useful http://stackoverflow.com/questions/34402080/suffix-array-construction-on-logn-competitive-programming-3-steven-halim take care case CCCCC with sentinel character Last edit: 2016-03-22 16:37:50 |
|||||||||
|
2016-01-20 17:07:32 Dhawal Harkawat
Optimized nlog^2n gets passed in 0.12s, while nlogn passes in 0.14s. I dont know why?? |
|||||||||
|
2015-12-30 22:43:11
nlogn(used radix sort everytime) with pointer optimisation got accepted though 0.27 seconds :( ,any ideas for better implementation Last edit: 2015-12-30 22:43:54 |
|||||||||
|
2015-12-23 10:47:00 Divyansh Shukla
For java, use the O(n) version. It got AC in 0.15s |
|||||||||
|
2015-08-26 21:13:54
Takes 0.5s in java! anybody managed in java? |
|||||||||
|
2015-08-21 19:33:59 (Tjandra Satria Gunawan)(曾毅昆)
Seems that Rodrigo Horruitiner was right and my previous summary comment on this problem is wrong, O(n) is slower than O(n*log(n)) because of radix constant :p |
|||||||||
|
2015-08-18 19:17:58 poojan
O(n*log n*log n) giving tle: |
|||||||||
|
2015-08-01 20:56:08 Obliterator
Yup. had to use suffix array with counting sort to get AC. Still wondering how did Manoj Kumar get AC with brute force. EDIT: Apparently we have to use Kasai's algorithm in LCP array construction to get AC in O(nlog^2n) Last edit: 2015-08-02 14:55:13 |
|||||||||
RSS