On Nov 29, 11:43 pm, Bearophile <bearophileh...@lycos.com> wrote: > Anyway, you may try a pure-Python2.x > implementation:http://suffixtree.googlecode.com/files/suffixtree-0.1.py
Ouch, Bearie... 214 lines of code are there. Ok.. I tested it. Firstly I replaced all "print " with "pass##print " (aiming to avoid intensive printing from inside of the code). Then I left in its final part only building of suffix trees. ================================================================== ... ... ... from time import time t = time() import sys sys.stdin = open('D:/88.txt', 'rt') f = sys.stdin.read().split() sys.stdin.close() z = open('D:/99.txt', 'wt') for tc in range(int(f[0])): s = f[tc + 1] test_str = s + '$' POSITIVE_INFINITY = len(test_str) - 1 suffix_tree = SuffixTree(test_str) print >> z, 'len(s) =', len(s) print >> z, 'time =', time() - t z.close() ============================================================ Output: ============================================================ len(s) = 1000 len(s) = 1000 len(s) = 10000 time = 0.641000032425 ============================================================ 0.64s > 0.48s (of my algo) I.e. the code can't help in my very special and narrow case. But of course it is worthy to be studied and memoized. E.g.: from huge string "s" we built its Suffix Tree. Now we are given arbitrary string "ss". Task: to find the largest its prefix occured in "s", traversing its Suffix Tree. -- http://mail.python.org/mailman/listinfo/python-list