在Boyer-Moore字符串搜索算法中计算第二个（不匹配）表

Question

为了让Boyer-Moore算法在最坏情况下运行时间是线性的，计算不匹配表的时间复杂度必须是O(m)。但是，如果用一种简单的方法来实现，就会对每个后缀进行O(m)的循环，同时检查这个后缀可能出现的所有位置是否相等……这样一来，时间复杂度就变成了O(m³)！

下面是这种简单实现的表构建算法。所以问题就变成了：我该如何把这个算法的运行时间改进到O(m)呢？

def find(s, sub, no):
    n = len(s)
    m = len(sub)

    for i in range(n, 0, -1):
        if s[max(i-m, 0): i] == sub[max(0, m-i):] and \
            (i-m < 1 or s[i-m-1] != no):
            return n-i

    return n

def table(s):
    m = len(s)
    b = [0]*m

    for i in range(m):
        b[i] = find(s, s[m-i:], s[m-i-1])

    return b

print(table('anpanman'))

为了让大家放心，这不是作业。我会在有人提出改进建议时进行更新。

Answer 1

在这个页面上，“为好后缀启发式处理的代码”部分展示了如何在O(n)的时间内构建好后缀表。页面上也解释了这段代码是怎么工作的。