字符串匹配的博耶摩尔。.字符数

Question

在使用博耶摩尔算法的许多示例中，声明了256个字符，我不知道该数字表示什么。.请帮助

来自（https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm）的示例：

function preprocess(pattern)
    T ← new table of 256 integers
    for i from 0 to 256 exclusive
        T[i] ← length(pattern)
    for i from 0 to length(pattern) - 1 exclusive
        T[pattern[i]] ← length(pattern) - 1 - i
    return T

Answer 1

正在声明字母中包含256个字符。

此一字节限制对ASCII来说很好用。但是，如果需要Unicode，则表T中还需要更多空间。实际上，这种空间依赖性对于算法分析至关重要。

如Wikipedia文章所述：

[算法为时间交换空间以在随机文本上获得O(n)的平均情况复杂度，尽管在最坏的情况下它具有O(nm)，其中模式的长度为m，而长度为搜索字符串为n。

Boyer-Moore平均为O(n+m)，因此理论上更快。在最佳情况下，它们是相同的，在病理情况下，BMH可能比BM更多地偏离轨道。但是实际上，Boyer-Moore-Horspool的实现速度更快，因为它明智地利用了空间。这使我们回到该表T。

固定大小表已过时。您可能会使用dict或HashMap或您选择的任何语言来代替。

对于捕获所有Unicode字符而言，这大大降低了表的成本。实际上，它使空间使用率从O(v)降低到O(min(v, n+m))。

请小心使用哈希支持的数据结构，以免在运行时意外添加一些log(v)因素（或更糟糕的因素）。