[算法] KMP

def getNext(pattern):
    j = 0
    p_len = len(pattern)
    next = [0]
    for i in range(1, p_len):
        while j > 0 and pattern[i] != pattern[j]:
            j = next[j-1]
        if pattern[i] == pattern[j]:
            j = j + 1
        next.append(j)
    return next

def kmp_search(text, pattern, next):
    j = 0
    plen = len(pattern)
    tlen = len(text)

    for i in range(0, tlen):
        while j > 0 and text[i] != pattern[j]:
            j = next[j-1]

        if text[i] == pattern[j] :
            j = j + 1

        if j == plen :
            print("from ", i-j+1, "to ", i)
            j = next[j-1]

text = ("aaaaaaaaaaaaaaaaaaaab")
pattern = ("aaab")

text1 = ("abababababababababa")
pattern1 = ("ababab")

next = getNext(pattern)
print(next)
kmp_search(text, pattern, next)
print(text)
print(pattern)

next1 = getNext(pattern1)
print(next1)
kmp_search(text1, pattern1, next1)
print(text1)
print(pattern1)