TheAlgorithms-Python

1
"""
2
Bitap exact string matching
3
https://en.wikipedia.org/wiki/Bitap_algorithm
4

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

8
Complexity: O(m*n)
9
    n = length of text
10
    m = length of pattern
11

12
Python doctests can be run using this command:
13
python3 -m doctest -v bitap_string_match.py
14
"""
15

16

17
def bitap_string_match(text: str, pattern: str) -> int:
18
    """
19
    Retrieves the index of the first occurrence of pattern in text.
20

21
    Args:
22
        text: A string consisting only of lowercase alphabetical characters.
23
        pattern: A string consisting only of lowercase alphabetical characters.
24

25
    Returns:
26
        int: The index where pattern first occurs. Return -1  if not found.
27

28
    >>> bitap_string_match('abdabababc', 'ababc')
29
    5
30
    >>> bitap_string_match('aaaaaaaaaaaaaaaaaa', 'a')
31
    0
32
    >>> bitap_string_match('zxywsijdfosdfnso', 'zxywsijdfosdfnso')
33
    0
34
    >>> bitap_string_match('abdabababc', '')
35
    0
36
    >>> bitap_string_match('abdabababc', 'c')
37
    9
38
    >>> bitap_string_match('abdabababc', 'fofosdfo')
39
    -1
40
    >>> bitap_string_match('abdab', 'fofosdfo')
41
    -1
42
    """
43
    if not pattern:
44
        return 0
45
    m = len(pattern)
46
    if m > len(text):
47
        return -1
48

49
    # Initial state of bit string 1110
50
    state = ~1
51
    # Bit = 0 if character appears at index, and 1 otherwise
52
    pattern_mask: list[int] = [~0] * 27  # 1111
53

54
    for i, char in enumerate(pattern):
55
        # For the pattern mask for this character, set the bit to 0 for each i
56
        # the character appears.
57
        pattern_index: int = ord(char) - ord("a")
58
        pattern_mask[pattern_index] &= ~(1 << i)
59

60
    for i, char in enumerate(text):
61
        text_index = ord(char) - ord("a")
62
        # If this character does not appear in pattern, it's pattern mask is 1111.
63
        # Performing a bitwise OR between state and 1111 will reset the state to 1111
64
        # and start searching the start of pattern again.
65
        state |= pattern_mask[text_index]
66
        state <<= 1
67

68
        # If the mth bit (counting right to left) of the state is 0, then we have
69
        # found pattern in text
70
        if (state & (1 << m)) == 0:
71
            return i - m + 1
72

73
    return -1
74

75

76
if __name__ == "__main__":
77
    import doctest
78

79
    doctest.testmod()
80