查找給定字符串中的所有重複子字符串

我無意中遇到了一個採訪問題：查找給定字符串中最小大小爲2的所有重複子字符串。該算法應該是高效的。查找給定字符串中的所有重複子字符串

以上問題的代碼在下面給出，但效率不高。

#include <iostream> 
#include <algorithm> 
#include <iterator> 
#include <set> 
#include <string> 

using namespace std; 

int main() 
{ 
    typedef string::const_iterator iterator; 
    string s("ABCFABHYIFAB"); 
    set<string> found; 

    if (2 < s.size()) 
     for (iterator i = s.begin() + 1, j = s.end(); i != j; ++i) 
      for (iterator x = s.begin(); x != i; ++x) 
      { 
       iterator tmp = mismatch(i, j, x).second;; 
       if (tmp - x > 1) 
        found.insert(string(x, tmp)); 
      } 

      copy(found.begin(), found.end(),ostream_iterator<string>(cout, "\n")); 
}

我的問題是，是否有可在時間實現上述問題的 O（N）的複雜性的任何數據結構？

如果你的答案是後綴樹或哈希請詳細說明。

來源

2012-04-07 IndieProgrammer

如果我理解正確，你會認爲輸出中有兩個不同的子字符串，如果它們的開始索引不同，而不是它們的內容不同，對嗎？ – Skiminok 2012-04-07 14:16:41

閱讀後綴樹，在我看來，wiki是一個很好的開始：http：//en.wikipedia。org/wiki/Suffix_tree – dexametason 2012-04-07 14:28:39

@dexametason您正在提出最佳解決方案。重複子字符串是CS中非常常見的問題。你能把這個作爲解決方案發布嗎？這對網站訪客會有幫助。乾杯! – 2012-04-08 08:53:04

如果你分析的字符串"AAAAAAAAAAAAAA"輸出，那麼在它O（N²）字符，所以算法至少是O（N²）。爲了實現O（n²），只需爲每個後綴s（索引[1..n]，[2..n]，[3..n]，...，[n]）構建suffix tree。 .N]）。如果其中一個字符串沒有自己的末端節點，則無關緊要，只需計算每個節點的使用頻率即可。

最後，迭代count> 1的每個節點並打印其路徑。

來源

2012-04-07 14:36:53 ipc

這只是一個瘋狂的想法，但值得一試（但是，它消耗O（N）內存，其中N是主字符串的長度）。該算法不是O（N），但也許可以優化。

這個想法是，你不想經常進行字符串比較。您可以收集讀取數據的散列（例如，讀取字符的ASCII碼的總和）並比較散列。如果散列值相等，則字符串可能與相等（它必須稍後檢查）。例如：

ABCAB 

A -> (65) 
B -> (131, 66) 
C -> (198, 133, 67) 
A -> (263, 198, 132, 65) 
B -> (329, 264, 198, 131, 66)

因爲你只關心2+長度值，你必須忽略最後一個值（因爲它總是對應於單個字符）。

我們看到兩個相同的值：131和198.131代表AB，並且顯示了這一對，但是198代表ABC和BCA，它們必須被人工檢查拒絕。

這只是想法，而不是解決方案本身。散列函數可以擴展到考慮字符在子串（或序列結構）中的位置。哈希值的存儲方法可能會改變，以提高性能（但增加內存使用的成本）。

希望我幫助一點點:)

來源

2012-04-07 14:33:48 Spook

我不知道後綴樹如何讓所有的重複串，串「密西西比」構建後綴樹是這樣的：

對不起，我明白了。「最後，用count> 1遍歷每個節點並打印它的路徑。」「count」是多少個這個子節點

tree-->|---mississippi    m..mississippi 
     | 
     |---i-->|---ssi-->|---ssippi i .. ississippi 
     |  |   | 
     |  |   |---ppi  issip,issipp,issippi 
     |  | 
     |  |---ppi    ip, ipp, ippi 
     | 
     |---s-->|---si-->|---ssippi s .. ssissippi 
     |  |  | 
     |  |  |---ppi  ssip, ssipp, ssippi 
     |  | 
     |  |---i-->|---ssippi  si .. sissippi 
     |    | 
     |    |---ppi  sip, sipp, sippi 
     | 
     |---p-->|---pi     p, pp, ppi 
       | 
       |---i     p, pi 

--- Suffix Tree for "mississippi" ---

來源

2012-04-15 10:16:23 ltqin

我覺得這個問題也可以用動態規劃來解決。

來源

2015-06-20 05:28:17

查找給定字符串中的所有重複子字符串

回答

相關問題