Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Number of distinct substrings of a string [continuation]

Reply
Thread Tools

Number of distinct substrings of a string [continuation]

 
 
n00m
Guest
Posts: n/a
 
      11-30-2009
On Nov 29, 11:43*pm, Bearophile <(E-Mail Removed)> wrote:
> Anyway, you may try a pure-Python2.x implementation:http://suffixtree.googlecode.com/fil...fixtree-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.




 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
number of distinct elements in a const container and iterating over the distinct elements Hicham Mouline C++ 1 04-11-2010 10:56 AM
Is there a command that returns the number of substrings in a string? Peng Yu Python 0 10-24-2009 02:31 AM
Replacing palindrome substrings of an input string with a given string Tung Chau C Programming 1 08-06-2004 07:27 PM
Replacing palindrome substrings of an input string with a given string. Any effecient algorithm? Tung Chau C Programming 0 08-06-2004 10:18 AM
splitting string with unknown number of similar substrings Jan Biel Perl Misc 2 04-02-2004 05:43 PM



Advertisments