numbers of alphabet which we call base modulus to hash a string the rabinkarp algorithm for finding a pattern within a piece of text with complexity onm most efficient when it is used with multiple patterns as it is able to check if any of a set of patterns match a section of text in o1 given the precomputed hashes this will be the simple version which only assumes one pattern is being searched for but it s not hard to modify 1 calculate pattern hash 2 step through the text one character at a time passing a window with the same length as the pattern calculating the hash of the text within the window compare it with the hash of the pattern only testing equality if the hashes match calculating the hash of pattern and substring of text calculate the https en wikipedia orgwikirollinghash testrabinkarp success test 1 test 2 test 3 test 4 test 5 numbers of alphabet which we call base modulus to hash a string the rabin karp algorithm for finding a pattern within a piece of text with complexity o nm most efficient when it is used with multiple patterns as it is able to check if any of a set of patterns match a section of text in o 1 given the precomputed hashes this will be the simple version which only assumes one pattern is being searched for but it s not hard to modify 1 calculate pattern hash 2 step through the text one character at a time passing a window with the same length as the pattern calculating the hash of the text within the window compare it with the hash of the pattern only testing equality if the hashes match calculating the hash of pattern and substring of text calculate the https en wikipedia org wiki rolling_hash test_rabin_karp success test 1 test 2 test 3 test 4 test 5
alphabet_size = 256

modulus = 1000003


def rabin_karp(pattern: str, text: str) -> bool:
    
    p_len = len(pattern)
    t_len = len(text)
    if p_len > t_len:
        return False

    p_hash = 0
    text_hash = 0
    modulus_power = 1

    
    for i in range(p_len):
        p_hash = (ord(pattern[i]) + p_hash * alphabet_size) % modulus
        text_hash = (ord(text[i]) + text_hash * alphabet_size) % modulus
        if i == p_len - 1:
            continue
        modulus_power = (modulus_power * alphabet_size) % modulus

    for i in range(t_len - p_len + 1):
        if text_hash == p_hash and text[i : i + p_len] == pattern:
            return True
        if i == t_len - p_len:
            continue
        
        text_hash = (
            (text_hash - ord(text[i]) * modulus_power) * alphabet_size
            + ord(text[i + p_len])
        ) % modulus
    return False


def test_rabin_karp() -> None:
    
    
    pattern = "abc1abc12"
    text1 = "alskfjaldsabc1abc1abc12k23adsfabcabc"
    text2 = "alskfjaldsk23adsfabcabc"
    assert rabin_karp(pattern, text1)
    assert not rabin_karp(pattern, text2)

    
    pattern = "ABABX"
    text = "ABABZABABYABABX"
    assert rabin_karp(pattern, text)

    
    pattern = "AAAB"
    text = "ABAAAAAB"
    assert rabin_karp(pattern, text)

    
    pattern = "abcdabcy"
    text = "abcxabcdabxabcdabcdabcy"
    assert rabin_karp(pattern, text)

    
    pattern = "Lü"
    text = "Lüsai"
    assert rabin_karp(pattern, text)
    pattern = "Lue"
    assert not rabin_karp(pattern, text)
    print("Success.")


if __name__ == "__main__":
    test_rabin_karp()