Why KMP is so slow.


  • 0
    D

    So I solved the problem with KMP algorithm, using Python, but it only beats 30%, and I'm pretty confused. Is KMP supposed to be faster than naive comparison?
    Here is my python KMP

    text = haystack
    pattern = needle
    if not text or not pattern:
        return 0 if text == pattern or not pattern else -1
    
    # pre-process. O(len(pattern))
    i, j = -1, 0
    t = [0] * len(pattern)
    t[0] = -1
    while j < len(pattern) - 1:
        if pattern[i] == pattern[j] or i == -1:
            i += 1
            j += 1
            t[j] = i
        else:
            i = t[i]
    i = j = 0
    
    # matching. O(len(text))
    while i < len(text) and j < len(pattern):
        if text[i] == pattern[j] or j == -1:
            j += 1
            i += 1
        else:
            j = t[j]
    return i - j if j == len(pattern) else -1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.