On 11/28/2009 1:51 AM, n00m wrote:
On Nov 27, 1:22 pm, Jon Clements<jon...@googlemail.com> wrote:
Of course, if you take '~' literally (len(s)<= -10001) I reckon
you've got way too many :)
Jon.
Then better: len(s)< abs(~10000)
PS It's a hard problem; so let's leave it alone
I'm not going to write it, but I guess a fairly efficient solution can
be written with using a Trie: http://en.wikipedia.org/wiki/Trie
and iterating over its items, including partial prefixes.
Worse case scenario for creating the tree would be O(n**2) where n =
length of string, and iterating the structure would take O(N) where N =
number of different substring.
for "abbaz", the data structure would be:
{'a': {'b': {'b': {'a': {'z': None}}},
'z': None,
},
'b': {'b': {'a': {'z': None}},
'a': {'z': None}},
},
'z': None,
}
iterating the structure:
a
ab
abb
abba
abbaz
az
b
bb
bba
bbaz
ba
baz
z
---
13 (not including '')
Now, this makes me interested. How efficient it would be when len(s) ==
10000... might as well write it and see. Take back what I said, give me
a minute...
--
http://mail.python.org/mailman/listinfo/python-list
