Python 实现 KMP 算法

Haystack ：需要搜索给定模式的字符串。
针 ：要搜索的模式。

时间复杂度 ：搜索部分（strstr 方法）具有复杂度 O(n)，其中 n 是 haystack 的长度但是针也被预先解析为构建前缀表 O(m) 是构建前缀表所必需的，其中 m 是长度针。
因此，KMP 的总时间复杂度为 O（n + m）
空间复杂度 ： **O(m)，**因为针上有前缀表。

注意：以下实现返回 haystack 中匹配的起始位置（如果匹配）else 返回 -1，对于边缘情况，例如，如果 needle / haystack 是空字符串或在 haystack 中找不到针。

def get_prefix_table(needle):
    prefix_set = set()
    n = len(needle)
    prefix_table = [0]*n
    delimeter = 1
    while(delimeter<n):
        prefix_set.add(needle[:delimeter])
        j = 1
        while(j<delimeter+1):
            if needle[j:delimeter+1] in prefix_set:
                prefix_table[delimeter] = delimeter - j + 1
                break
            j += 1
        delimeter += 1
    return prefix_table

def strstr(haystack, needle):
    # m: denoting the position within S where the prospective match for W begins
    # i: denoting the index of the currently considered character in W.
    haystack_len = len(haystack)
    needle_len = len(needle)
    if (needle_len > haystack_len) or (not haystack_len) or (not needle_len):
        return -1
    prefix_table = get_prefix_table(needle)
    m = i = 0
    while((i<needle_len) and (m<haystack_len)):
        if haystack[m] == needle[i]:
            i += 1
            m += 1
        else:
            if i != 0:
                i = prefix_table[i-1]
            else:
                m += 1
    if i==needle_len and haystack[m-1] == needle[i-1]:
        return m - needle_len
    else:
        return -1

if __name__ == '__main__':
    needle = 'abcaby'
    haystack = 'abxabcabcaby'
    print strstr(haystack, needle)