dimanche 19 avril 2015

worst-case time complexity of str.find in python

The question is already in the title, what is the worst-case time complexity of the C implementation of str.find(string, substring) in Python if n is the length of string and m is the length of substring? The source code (http://ift.tt/1baWVqr) seems to talk about the boyer-moore-horspool algorithm, which according to Wikipedia has a worst-case complexity of O(m*n).


Aucun commentaire:

Enregistrer un commentaire