Preprocess string for efficient search

Question

I have a fixed string S of size n on which I make a lot of substring queries. One way to optimise for this situation is to preprocess the string and build a suffix tree, or suffix array. After preprocessing, substring queries can be performed optimally on S.

Is there an easy way, in Python, to preprocess strings "out of the box", without having to manually write all the code to build a suffix tree or suffix array?

Spike Gronim · Accepted Answer · 2012-02-21 01:07:46Z

3

I believe that the emsre python package provides exactly what you are looking for.

answered Feb 21, 2012 at 1:07

Spike Gronim

6,20225 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Randomblue Over a year ago

I'm playing around at interviewstreet.com

WestCoastProjects Over a year ago

It would be nice to see an answer that does it without an assist from a (likely complex) library. Basically - is there a solution that we can grok in O(1) time

Collectives™ on Stack Overflow

Preprocess string for efficient search

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related