Source code for algorithms.searching.kmp_search

"""

    KMP Search
    ----------
    Implementation of kmp search on string. Uses a prefix function to reduce
    the searching time.

    Time Complexity:  O(n + k), where k is the substring to be found

    Psuedo Code: CLRS. Introduction to Algorithms. 3rd ed.

"""



[docs]def compute_prefix(word): """ Returns the prefix of the word. :param word: The sub string that the prefix will be computed for. :rtype: Returns computed prefix of the word. """ word_length = len(word) prefix = [0] * word_length k = 0 for q in range(1, word_length): while k > 0 and word[k] != word[q]: k = prefix[k - 1] if word[k + 1] == word[q]: k = k + 1 prefix[q] = k return prefix