Number of distinct substrings of a string [continuation]

Bearophile bearophileHUGS at lycos.com
Sun Nov 29 16:43:17 EST 2009


n00m:

> I suspect that building of Suffix Tree would
> be a big exec.time-consuming overhead

In C/D/C++ there are ways to allocate memory in smarter ways, using
pools, arenas, stacks, freelists, etc. With that, using a compact
encoding of tree nodes (there are many different tricks to reduce
space used by a suffix tree), you can go fast enough. Probably a basic
implementation too will suffice in many cases :-)

Anyway, you may try a pure-Python2.x implementation:
http://suffixtree.googlecode.com/files/suffixtree-0.1.py
If you find time & will to try to use that (or similar code) to
improve your Python solution to the problem 99, you can show us the
code here...

Bye,
bearophile



More information about the Python-list mailing list