Python Programming Challenges for beginners?

[Lie Ryan]

On 11/28/2009 1:51 AM, n00m wrote:
> On Nov 27, 1:22 pm, Jon Clements<jon... at 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...