Python string ‘in’ operator implementation algorithm and time complexity

by

It’s a combination of Boyer-Moore and Horspool.

You can view the C code here:

Fast search/count implementation, based on a mix between Boyer-Moore and Horspool, with a few more bells and whistles on the top. For some more background, see: https://web.archive.org/web/20201107074620/http://effbot.org/zone/stringlib.htm.

From the link above:

When designing the new algorithm, I used the following constraints:

  • should be faster than the current brute-force algorithm for all test cases (based on real-life code), including Jim Hugunin’s worst-case test
  • small setup overhead; no dynamic allocation in the fast path (O(m) for speed, O(1) for storage)
  • sublinear search behaviour in good cases (O(n/m))
  • no worse than the current algorithm in worst case (O(nm))
  • should work well for both 8-bit strings and 16-bit or 32-bit Unicode strings (no O(σ) dependencies)
  • many real-life searches should be good, very few should be worst case
  • reasonably simple implementation

More Related Contents:

  1. Find common substring between two strings
  2. Is the time-complexity of iterative string append actually O(n^2), or O(n)?
  3. Find longest repetitive sequence in a string
  4. Python string with space and without space at the end and immutability
  5. When splitting an empty string in Python, why does split() return an empty list while split(‘\n’) returns [”]?
  6. How to test if one string is a subsequence of another? [duplicate]
  7. Python: find closest string (from a list) to another string
  8. String similarity metrics in Python [duplicate]
  9. How can I interleave or create unique permutations of two strings (without recursion)
  10. Why is it string.join(list) instead of list.join(string)?
  11. How to convert string representation of list to a list?
  12. Comparing a string to multiple items in Python
  13. Remove unwanted parts from strings in a column
  14. Join a list of items with different types as string in Python
  15. Good Python modules for fuzzy string comparison? [closed]
  16. Split a string at uppercase letters
  17. How did Python implement the built-in function pow()?
  18. Python float – str – float weirdness
  19. Splitting a string by list of indices
  20. Converting a column within pandas dataframe from int to string
  21. efficiently checking that string consists of one character in Python
  22. Are strings cached? [duplicate]
  23. Print very long string completely in pandas dataframe
  24. Remove duplicate chars using regex?
  25. How to remove leading and trailing zeros in a string? Python
  26. I have a string whose content is a function name, how to refer to the corresponding function in Python?
  27. How to check a string for a special character?
  28. Python: powerset of a given set with generators [duplicate]
  29. How to use str.contains() with multiple expressions in pandas dataframes
  30. How to merge two json string in Python?

Leave a Comment