given two strings text and pattern return the list of start indexes in text that matches with the pattern using knuthmorrispratt algorithm args text text to search pattern pattern to search in the text returns list of indices of patterns found example knuthmorrispratt hello there hero he 0 7 12 if idx is in the list textidx idx m matches with pattern time complexity of the algorithm is onm with n and m the length of text and pattern respectively making pi table finding pattern given two strings text and pattern return the list of start indexes in text that matches with the pattern using knuth_morris_pratt algorithm args text text to search pattern pattern to search in the text returns list of indices of patterns found example knuth_morris_pratt hello there hero he 0 7 12 if idx is in the list text idx idx m matches with pattern time complexity of the algorithm is o n m with n and m the length of text and pattern respectively making pi table finding pattern
from typing import Sequence, List

def knuth_morris_pratt(text : Sequence, pattern : Sequence) -> List[int]:
    
    n = len(text)
    m = len(pattern)
    pi = [0 for i in range(m)]
    i = 0
    j = 0
    
    for i in range(1, m):
        while j and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            pi[i] = j
    
    j = 0
    ret = []
    for i in range(n):
        while j and text[i] != pattern[j]:
            j = pi[j - 1]
        if text[i] == pattern[j]:
            j += 1
            if j == m:
                ret.append(i - m + 1)
                j = pi[j - 1]
    return ret