bitap exact string matching https en wikipedia orgwikibitapalgorithm 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 omn n length of text m length of pattern python doctests can be run using this command python3 m doctest v bitapstringmatch py 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 bitapstringmatch abdabababc ababc 5 bitapstringmatch aaaaaaaaaaaaaaaaaa a 0 bitapstringmatch zxywsijdfosdfnso zxywsijdfosdfnso 0 bitapstringmatch abdabababc 0 bitapstringmatch abdabababc c 9 bitapstringmatch abdabababc fofosdfo 1 bitapstringmatch abdab fofosdfo 1 initial state of bit string 1110 bit 0 if character appears at index and 1 otherwise for the pattern mask for this character set the bit to 0 for each i the character appears if this character does not appear in pattern it s pattern mask is 1111 performing a bitwise or between state and 1111 will reset the state to 1111 and start searching the start of pattern again if the mth bit counting right to left of the state is 0 then we have found pattern in text 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 initial state of bit string 1110 bit 0 if character appears at index and 1 otherwise 1111 for the pattern mask for this character set the bit to 0 for each i the character appears if this character does not appear in pattern it s pattern mask is 1111 performing a bitwise or between state and 1111 will reset the state to 1111 and start searching the start of pattern again if the mth bit counting right to left of the state is 0 then we have found pattern in text
def bitap_string_match(text: str, pattern: str) -> int:
    
    if not pattern:
        return 0
    m = len(pattern)
    if m > len(text):
        return -1

    
    state = ~1
    
    pattern_mask: list[int] = [~0] * 27  

    for i, char in enumerate(pattern):
        
        
        pattern_index: int = ord(char) - ord("a")
        pattern_mask[pattern_index] &= ~(1 << i)

    for i, char in enumerate(text):
        text_index = ord(char) - ord("a")
        
        
        
        state |= pattern_mask[text_index]
        state <<= 1

        
        
        if (state & (1 << m)) == 0:
            return i - m + 1

    return -1


if __name__ == "__main__":
    import doctest

    doctest.testmod()