| 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-01-02 22:42:54 (Tjandra Satria Gunawan)(曾毅昆)
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 |
|||||||||
|
2014-10-23 21:11:03 Gaurav Babbar
SAM is givig TLE! what is the size of the input alphabet set?? ---- AC after optimisatons :) Last edit: 2014-10-24 21:15:36 |
|||||||||
|
2014-10-23 18:59:07 Varun Gambhir
n*logn*logn algorithm for building suffix array gives tle :( |
|||||||||
|
2014-05-13 14:48:00 Ashish Kumar
Used suffix array with qsort function but it is giving tle?? Last edit: 2014-05-13 14:48:16 |
|||||||||
|
2014-04-26 06:07:37 yhylord
Can SAM solve this problem? If S contains all characters in ASCII,then SAM will get MLE(TLE)... -------- Now I've got TLE. How many cases does it has? Last edit: 2014-04-29 14:35:19 |
|||||||||
|
2014-03-12 04:21:36 innovolt
simple 1 .........sufffixxxxx array |
|||||||||
|
2013-08-28 12:53:17 aar
Suffix Array with O(n * logn *logn) is accepted... |
|||||||||
|
2013-07-17 07:26:55 jimmy
O(N*Log(N)^2) gets TLE.. @Jitendra i tried using qsort too. it gives TLE |
|||||||||
|
2014-03-07 11:01:43 aqfaridi
pointer arithmetic to speed up.. |
|||||||||
|
2013-04-18 04:35:07 Abdullah Enes ÖNCÜ
why I get a RTE? |
|||||||||
RSS