字符串两种前缀算法(z和kmp)

KMP字符串是数据结构课本上教过的，其实就是类似某种DP算法： `dp[i] = sz` 表示 `s[i-sz..i] = s[0..sz]` 基于KMP算法可以扩展出AC自动机算法：基于BFS算法来构建这个dp, 在AC里面这个dp叫做fail指针。在KMP里面也可以把这个叫做fail指针。KMP算法的好处就是可以只针对pattern做index, 这个和后面Z函数形成对比：Z函数如果要求解前缀的话需要同时对hay和needle同时做索引。

class KMP2:
    @staticmethod
    def build_fail(t):
        n = len(t)
        fail = [-1] * n
        p = -1
        for i in range(1, n):
            while t[i] != t[p + 1]:
                if p == -1: break
                p = fail[p]
            if t[i] == t[p + 1]:
                p += 1
            fail[i] = p
        return fail

    def __init__(self, t):
        self.t = t
        self.fail = self.build_fail(t)

    def search(self, s):
        fail, t = self.fail, self.t
        j = -1
        for i in range(len(s)):
            while s[i] != t[j + 1]:
                if j == -1: break
                j = fail[j]
            if s[i] == t[j + 1]:
                j += 1
            if (j + 1) == len(t):
                return i + 1 - len(t)
        return -1

另外一个前缀算法是Z函数，其中 `z[i]=sz` 表示从 i 开始最多可以和 0 开始匹配sz个字符串。 这里和KMP不同：KMP是知道当前位置结尾最多匹配多少，而Z函数是知道当前位置起始最多可以匹配多少。两种不同的语义都可以有效地求解出来。

def compute_z(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            # s[l..r] = s[0..r-l]
            # s[i..r] = s[i-l..r-l]
            # 所以z[i-l]是从s[i]作为起点的最大匹配距离
            # 但是这个匹配距离也收到r的限制.
            z[i] = min(z[i - l], r - i + 1)
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            l, r = i, i + z[i]
            z[i] += 1
    return z

def index(s, p):
    m = len(p)
    z = zfunction(p + '$' + s)
    for i in range(m + 1, len(s) + len(p) + 1):
        if z[i] == m:
            return i - m - 1
    return -1