KMP算法

[bitmori]

KMP 關鍵在於跳轉表

next[i] = len(p[0..<i]的最長prefix同時也是suffix)

len(next) = len(p) + 1

[bitmori]

def build(p):
    m = len(p)
    nxt = [0, 0]
    j = 0
    for i in range(1, m):
        while j > 0 and p[i] != p[j]:
            j = nxt[j]
        if p[i] == p[j]:
            j += 1
        nxt.append(j)
    return nxt

def kmp(s, p):
    res = []
    nxt = build(p)
    j = 0
    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = nxt[j]
        if s[i] == p[j]:
            j += 1
        if j == len(p):
            res.append(i - j + 1)
            j = nxt[j]
    return res