the knuthmorrispratt algorithm for finding a pattern within a piece of text with complexity on m 1 preprocess pattern to identify any suffixes that are identical to prefixes this tells us where to continue from if we get a mismatch between a character in our pattern and the text 2 step through the text one character at a time and compare it to a character in the pattern updating our location within the pattern if necessary kmp knuthmorrispratt all knuthmorrisprattkmp s kmp finds for s in kn hm rr tt not there true 1 construct the failure array 2 step through text searching for pattern if this is a prefix in our pattern just go back far enough to continue calculates the new index we should go to if we fail a comparison param pattern return test 1 test 2 test 3 test 4 test 5 doctests test 6 the knuth morris pratt algorithm for finding a pattern within a piece of text with complexity o n m 1 preprocess pattern to identify any suffixes that are identical to prefixes this tells us where to continue from if we get a mismatch between a character in our pattern and the text 2 step through the text one character at a time and compare it to a character in the pattern updating our location within the pattern if necessary kmp knuth_morris_pratt all knuth_morris_pratt kmp s kmp find s for s in kn h_m rr tt not there true 1 construct the failure array 2 step through text searching for pattern index into text pattern if this is a prefix in our pattern just go back far enough to continue calculates the new index we should go to if we fail a comparison param pattern return test 1 test 2 test 3 test 4 test 5 doctests test 6
from __future__ import annotations


def knuth_morris_pratt(text: str, pattern: str) -> int:
    

    
    failure = get_failure_array(pattern)

    
    i, j = 0, 0  
    while i < len(text):
        if pattern[j] == text[i]:
            if j == (len(pattern) - 1):
                return i - j
            j += 1

        
        
        elif j > 0:
            j = failure[j - 1]
            continue
        i += 1
    return -1


def get_failure_array(pattern: str) -> list[int]:
    
    failure = [0]
    i = 0
    j = 1
    while j < len(pattern):
        if pattern[i] == pattern[j]:
            i += 1
        elif i > 0:
            i = failure[i - 1]
            continue
        j += 1
        failure.append(i)
    return failure


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    
    pattern = "abc1abc12"
    text1 = "alskfjaldsabc1abc1abc12k23adsfabcabc"
    text2 = "alskfjaldsk23adsfabcabc"
    assert knuth_morris_pratt(text1, pattern)
    assert knuth_morris_pratt(text2, pattern)

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

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

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

    
    kmp = "knuth_morris_pratt"
    assert all(
        knuth_morris_pratt(kmp, s) == kmp.find(s)
        for s in ("kn", "h_m", "rr", "tt", "not there")
    )

    
    pattern = "aabaabaaa"
    assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]