问题标签 [aho-corasick]

使用三叉树的 FSA 与将转换表实现为搜索树（例如 std::map）的 trie 有什么区别？看起来两者都具有读取一个符号的 O(log k) 复杂度和 O(S) 内存复杂度，其中 k 是字母大小，S 是所有接受的输入字符串的长度之和。

如果我们不需要自动机在运行时更改，那么最好的选择不是使用（符号，状态）转换对的排序向量以及二进制搜索吗？

I have a trouble with understanding this implementation of the Knuth-Morris-Pratt algorithm in Haskell.

http://twanvl.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell

In particular I don't understand the construction of the automaton. I know that it uses the "Tying the Knot" method to construct it, but it isn't clear to me and I also don't know why it should have the right complexity.

Another thing I would like to know is whether you think that this implementation could be easily generalized to implement the Aho-Corasick algorithm.

Thanks for your answers!

我对这个练习有疑问：

给定一个A到B的范围 ，1 <= A,B <= 10^18
以及一些表示子字符串的整数Ni，其中1 <= i <= 1000; 返回包含任何给定子字符串的 A,B（包括A和B
） 之间范围内的可能数字的总数。

输入

例如 ：

简单输入

简单输出

解释：从 10 到 22 的范围包含以下数字，10* 11* 12* 13* 14* 15* 16* 17* 18* 19* 20 21* 22包含子字符串 10 或 1 的有效数字标有 (*)

我们如何计算范围内可能数字的总数？

我在这学期学习算法，并阅读了关于Aho-Corasick 字符串匹配算法和Ukkonen构建后缀树的算法。

我阅读了它们，但无法理解这两者的主要基本区别，除了失败链接检查前缀和后缀链接检查后缀。

这两种算法有什么区别？

最近我尝试在centos5.8_x64和python2.7.5中使用ahocorasick，但是我发现结果异常，请告诉我原因吗？我发现该模块在我的windows 7和python2.7.5中完美运行。这里是我在 linux 中的测试代码和结果。

返回值应该是None，但我不知道为什么返回值似乎是溢出数？

我在这里使用了 python 包 ahocorasick( https://hkn.eecs.berkeley.edu/~dyoo/python/ahocorasick/ ) 来匹配州名的文本：

然后我尝试进行搜索

它返回

这是好的和合法的，但是当我这样做时

它应该返回一个 NONE 对象，但它返回：

以前有人遇到过这种情况吗？为什么会这样？

我无法理解以下用于使用 Aho-Corasick alg 进行字符串模式匹配的算法。

请帮助我了解 Aho-Corasick 算法中多个模式的状态转换表的构造。

请给出一个简单而详细的解释，以便我理解。

我正在关注这篇论文，这里是动画。

谢谢。

在 python 中使用 ahocorasick 模块添加到树时出现段错误，我尝试了 0.9 和 1.0pre 相同的结果，任何帮助将不胜感激。谢谢

我有一段 PHP 代码可以成功搜索数据中的$list关键字，$post并在相似度约为 80-90% 的地方回显结果。下面是代码：

现在，问题是我想使用用 Java 编写的 Aho-Corasick 库来搜索$list关键字。你可以在这里$fulltext找到代码。

所以，我的问题是如何调用 Aho-Corasick 库以搜索$list并$fulltext找到具有 100% 相似性的关键字。非常感谢您的帮助和时间。