python efficient substring search [duplicate]

Question

Possible Duplicate:
How is string.find implemented in CPython?

I have read many posts here in stack-overflow comparing the performance of sub-string search (e.g. Python string search efficiency, Is this the most efficient way to search for a substring?, substring in python, etc...)

I have also looked at the source code implementation of contains abstract.c.

As far as i see the built-in implementation is an iterative one : python docs

Does python have an implementation of more sufficient techniques for finding a substring: Boyer–Moore Algorithm, Rabin–Karp algorithm, etc... ???

EDIT

The question has been extended: Python: Improving sub-string search by embedding sophisticated algorithms.

@Martijn Pieters: notice that i have asked this question before you have added the link to string_contains. — Michael
– Michael, Commented Sep 3, 2012 at 10:20
@Martijn Pieters: It seems that for python 2.7 fastsearch doesn't implement Boyer–Moore (hg.python.org/cpython/file/2370e331241b/Objects/stringlib/…), am i wrong??? — Michael
– Michael, Commented Sep 4, 2012 at 7:06
Better make that a new question, not change the premise of the old one that's already been answered. :-) — Martijn Pieters
– Martijn Pieters, Commented Sep 4, 2012 at 7:20

georg · Accepted Answer · 2012-09-03 09:05:29Z

10

The actual cpython string search implementation is here:

http://hg.python.org/cpython/file/tip/Objects/stringlib/fastsearch.h

It appears to use Boyer-Moore.

answered Sep 3, 2012 at 9:05

georg

216k57 gold badges324 silver badges401 bronze badges

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

2 Comments

Michael Over a year ago

Thanks, i will accept this answer, although i am interested if there is such implementation also for Rabin Karp.

Martijn Pieters Over a year ago

See the comment on the other answer, it's not B-M, it's inspired (simplified) by B-M with some Horspool and Sunday thrown in. See effbot.org/zone/stringlib.htm.

user2665694 · Accepted Answer · 2012-09-03 09:03:02Z

1

The core implementation does not provide this level of functionality.

You will find implementations for Boyer-Moore or Rabin-Karp for Python using Google.

answered Sep 3, 2012 at 9:03

user2665694

1 Comment

jfs Over a year ago

While strictly speaking CPython doesn't use BMRK it can provide a sublinear performance (good thing) using algorithm based on BM: The stringlib Library

Collectives™ on Stack Overflow

python efficient substring search [duplicate]

2 Answers 2

2 Comments

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Linked

Related