string - 字符串匹配boyer moore..字符数
问题描述
在许多使用 Boyer moore 算法的示例中,有一个 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
解决方案
它声明字母表中有256
字符。
这一字节限制对 ASCII 来说效果很好。但是如果您需要 Unicode,那么您还需要在表格中留出更多空间T
。事实上,这种空间依赖性对于算法的分析是必不可少的。
正如维基百科文章所说:
该算法以空间换时间以获得
O(n)
随机文本的平均情况复杂度,尽管O(nm)
在最坏的情况下,模式m
的长度为 ,搜索字符串的长度为n
。
Boyer-Moore是O(n+m)
平均的,所以理论上更快。在最好的情况下它们是相同的,在病理情况下,BMH 可能比 BM 更容易出轨。但在实践中,Boyer-Moore-Horspool 的实现速度更快,因为它明智地使用了空间。这让我们回到那张桌子T
。
固定尺寸的桌子已经过时了。您可能会使用 adict
或 aHashMap
或任何您选择的语言来代替。
对于捕获所有 Unicode 字符的情况,这大大降低了表格的成本。事实上,它将空间使用率从 降低O(v)
到O(min(v, n+m))
.
请小心使用哈希支持的数据结构,这样您就不会意外log(v)
地在运行时添加一些因素(或更糟)。
推荐阅读
- c++ - 检查实现了哪些基类
- node.js - SyntaxError:块范围的声明 Ubuntu 16.04.4 LTS
- c - 将 Q18.2 转换为浮点数
- r - 使用 Shiny 中的可格式化表格手动设置条件格式边界
- java - 设置计数项目
- python - 如何更改熊猫数据框中的浮点数(科学值)?
- python - Django 2.0 URL:配置 urls.py 文件
- spring-boot - Spring Boot ws 中的内联 xsd 导入导致来自所有 wsdl 的消息类型和操作
- c++ - 如何声明用不同值内联初始化的结构的 std::array
- c++ - 在 C++ 中模拟 if __name__ == __main__ 会导致错误“未定义类似函数的宏”