Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

python efficient substring search [duplicate]

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.

like image 455
Michael Avatar asked Sep 03 '12 08:09

Michael


2 Answers

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.

like image 82
georg Avatar answered Nov 12 '22 08:11

georg


The core implementation does not provide this level of functionality.

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

like image 1
Andreas Jung Avatar answered Nov 12 '22 06:11

Andreas Jung