strings.bitap_string_match

Bitap exact string matching https://en.wikipedia.org/wiki/Bitap_algorithm

Searches for a pattern inside text, and returns the index of the first occurrence of the pattern. Both text and pattern consist of lowercase alphabetical characters only.

Complexity: O(m*n)

n = length of text m = length of pattern

Python doctests can be run using this command: python3 -m doctest -v bitap_string_match.py

Functions

bitap_string_match(→ int)

Retrieves the index of the first occurrence of pattern in text.

Module Contents

strings.bitap_string_match.bitap_string_match(text: str, pattern: str) → int

Retrieves the index of the first occurrence of pattern in text.

Args:

text: A string consisting only of lowercase alphabetical characters. pattern: A string consisting only of lowercase alphabetical characters.

Returns:

int: The index where pattern first occurs. Return -1 if not found.

>>> bitap_string_match('abdabababc', 'ababc')
5
>>> bitap_string_match('aaaaaaaaaaaaaaaaaa', 'a')
0
>>> bitap_string_match('zxywsijdfosdfnso', 'zxywsijdfosdfnso')
0
>>> bitap_string_match('abdabababc', '')
0
>>> bitap_string_match('abdabababc', 'c')
9
>>> bitap_string_match('abdabababc', 'fofosdfo')
-1
>>> bitap_string_match('abdab', 'fofosdfo')
-1