使用C++在文件中查找所有重複模式

我正在尋找一種方法來查找輸入文件中包含至少3個字符的所有重複序列，然後打印出最常見的模式！它似乎需要大量的字符串處理和通過輸入文件進行強烈搜索，這是因爲模式的最大尺寸沒有上限！使用C++在文件中查找所有重複模式

是否有任何有效的算法來做到儘可能少的處理和混亂？我應該用string.h還是用char數組更好？關於如何開始的任何提示/有幫助的片段等？

tnx

2012-06-19 Saba Ahang

你需要找到他們或最常見的？ –

你可以給預期的文件和輸出 – 2012-06-19 11:15:03

如果文件很小，你可以將它全部加載到內存中，所以你沒有頂幾次讀它。你也可以研究諸如[後綴樹]（http://en.wikipedia.org/wiki/Suffix_tree）？ –

我建議你從文件中創建一個後綴樹。這將在文件大小方面具有線性複雜性，並將解決問題。您可以稍微修改一下算法，以存儲除了字符串本身之外還有多少次字符串。這裏是一個great post解釋如何創建一個後綴樹。

2012-06-19 11:16:33

這種方法還可以讓你找到更長的序列，給出一些啓發式的方法來選擇它們;通過查找樹中節點的子節點，可以看到abc的大多數實例是否在abcd的字符串中，以及abcdefg等中的這些字符串。 –

如果您意識到最頻繁的序列長度爲4個字符，找到最頻繁的序列非常容易。它可以在O(n)時間完成，其中n是輸入文件的大小。

您可以構建一個std::map<string,int>，逐個字符迭代每次4個字符的序列，並使用地圖中相應的鍵增加值。

2012-06-19 11:17:57

問題指出，字符串的長度是無界的。如果你不能確定字符串的長度，那麼這種方法將不起作用。另外，您需要爲該文件中的每個字符添加4個字符。 – jlunavtgrad

@jlunavtgrad如果你只是尋找最常見的一個，那沒關係。最常見的子字符串長度爲4個字符。 –

回答