| 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
|
|||||||||
|
2013-03-09 04:07:18 Adel Ali
(N(LogN)^2) suffix array gives me TLE :S :S |
|||||||||
|
2013-02-13 07:33:26 Wing Gu
I use SAM.However,when I use array,I got TLE,when I use map,I got AC |
|||||||||
|
2012-11-23 18:20:02 Sanjary Rahman
Doubly Algo of suffix array took 0.01s for me :) |
|||||||||
|
2012-08-21 09:51:36 Daniel
Suffix Array can do it!It's the same as the problem 694.Suffix Array can solve it within only 0.4s. |
|||||||||
|
2012-06-15 04:02:04 bean
Why can I get AC in this problem but not in problem 694? Last edit: 2012-06-15 04:02:54 |
|||||||||
|
2011-08-03 13:41:26 Gaurav Menghani
I had to replace strlen by pointer arithmetic, and sort by qsort to get AC. Sigh :-( |
|||||||||
|
2011-07-28 08:19:53 Jitendra
qsort is faster than stl sort. stl sort gives tle while qsort soln accepted :) |
|||||||||
|
2011-07-09 22:55:14 Thomas Dybdahl Ahle
I would say "" is a substring of any string, but I notice it isn't counted in the examples. Or maybe its the string itself that isn't counted as a substring? |
|||||||||
|
2010-06-02 12:51:09 Leopoldo Taravilse
Do the strings contain the ' ' char? |
|||||||||
|
2010-02-25 15:45:52 lccycc
length is <= 50000 I know.. but it's no the problem I have open all arrays to 1100000 The problem is: it need long long for n and the output Last edit: 2010-02-25 16:06:39 |
|||||||||
RSS