查找字符串的字符串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. 如果這封信是比賽的一部分，那麼比賽包括所有字母，不論其在文本中的頻率。