查找字符串的字符串w /最低频字符

Question

我有3个文本文件。其中有一组文字，通过
（前。ABCDEAABBCCDDAABC）搜索
一个包含文本
（例如，AB，EA，CC）
而最后含有的频率来搜索一些模式每个字符的
（来自
A 4
B 4
-C 4
d 3
ë1
）
我试图写的算法来为每个模式找到最不频繁出现的字符并搜索字符串以查找这些事件，然后检查周围的字母以查看字符串是否匹配。目前，我分别在他们自己的载体中具有字符和频率。 （其中每个向量的i = 0将分别为A 4）

是否有更好的方法来做到这一点？也许更快的数据结构？还有，有什么有效的方法来检查模式字符串文本字符串一旦频率最低的信被发现？

Answer 1

你可以运行一个迭代循环，保持实例的计数，并有检查，看是否有文字出现次数超出基于总字符的百分比搜索更多和字符串的总长度。也就是说，如果你有100个字符，5点的可能性，已经出现了超过20％的百可以打折任何字符，由路过匹配一个任意值，提高了效率。

Answer 2

您可以运行Aho-Corasick算法。它的复杂性（一旦预处理 - 其复杂性是无关的文本 - 完成），是Θ（N + P），其中

• ñ是文本的长度

• p是匹配的总数发现

这基本上是最佳的。试图跳过看起来频繁的字母没有意义：

1. 如果字母不是匹配的一部分，算法需要单位时间。

2. 如果这封信是比赛的一部分，那么比赛包括所有字母，不论其在文本中的频率。