字符串中的子串計算

對於以下問題，我很難找到比O（n^2）更好的方法。字符串中的子串計算

我給了一個字符串，例如xyxxz。

現在我需要在給定字符串的每個前綴中找到匹配字符的總數。

這裏，字符串可能的前綴是：

xyxxz : matching characters is 5 
yxxz : matching characters is 0 (since 1st character doesnt match) 
xxz : matching characters is 1 
xz : matching characters is 1 
z  : matching characters is 0

這應該是輸出。我做了下面的代碼：

cin>>str; 
len=str.length(); 
for(i=0;i<len;i++){ 
    sum=0; 
    k=i; 
    for(int j=0;j<len;j++) 
    { 
     if(str[k] == str[j]){ 
      sum++; 
      k++; 
     } 
     else 
      break; 
    } 
    cout<<sum<<" "; //I get the output 5 0 1 1 0 
}

但它是爲O（n^2）。我想要一個更好的方法：可能是O（n）或O（nlogn）。

在此先感謝。

來源

2012-07-26 vijay

指出'std :: mismatch'，其中IIRC是線性複雜度。 – chris 2012-07-26 04:20:46

這會有所幫助。謝謝@chris :) – vijay 2012-07-26 04:24:49

如果你想要它，[這個頁面]（http://en.cppreference.com/w/cpp/algorithm/mismatch）有一個可能的實現。這是一個很好的開始，你可以在哪裏改進。 – chris 2012-07-26 04:25:59

int strcoll (register const char *s1, register const char *s2) 
{ 
    while (*s1 == *s2++) { 
     if (*s1++ == '\0') { 
      return 0; 
     } 
    } 
    return *s1 - *--s2; 
}

該函數開始比較每個字符串的第一個字符。如果它們彼此相等，則繼續使用以下對，直到字符不同或者直到出現指示字符串末尾的空字符。

返回表示字符串之間關係的整數值：零值表示兩個字符串相等。大於零的值表示不匹配的第一個字符在str1中比在str2中有更大的值;而小於零的值表示相反。

來源

2012-07-26 04:42:09 linsek

但它不會給出比O（n^2）更好的解決方案。您必須使用字符串和字符串的每個前綴來執行strcoll。因此，爲了得到每個前綴，然後strcoll，它將是O（n^2）。可以用strcmp或str.compare（）完成。 – vijay 2012-07-26 04:45:54

如果爲您的字符串構建後綴樹，則可以通過後綴樹來查找匹配的長度。任何與第一個字符不匹配的根節點的子節點將具有零值，其所有子節點的值都將爲零。然後，具有匹配的根節點的子節點的所有後代將至少具有等於該邊的匹配長度的匹配。

來源

2012-07-26 04:44:39

這是什麼將有所幫助。我需要遍歷後綴樹，並獲得每個前綴的邊緣總數，如果我得到你的想法。這將需要O（nlogn）。請糾正我，如果我得到錯誤。謝謝 – vijay 2012-07-26 04:48:41

@ vjshah：是的，這聽起來是對的。由於樹可以在O（n）時間內構建，所以它可能比O（n * log（n））做得更好，但我不確定。 – 2012-07-26 04:52:37

是的謝謝你的建議對我很有幫助。 :) – vijay 2012-07-26 04:53:51

我不擅長計算O值..但這裏是另一個你需要的實現。我認爲它更有效一些。

cin >> str; 

len=str.length(); 
for(i=0;i<len;i++) 
{ 
    sum=0; 
    k=0; 

    while(str[k + sum] == str[i + sum]) 
    { 
      sum++; 
    } 
    cout << sum ; 

}

來源

2012-07-26 05:14:29 ddb

雖然是一個無限循環。而且它又是O（n^2） – vijay 2012-07-26 07:20:21

這可以在線性時間使用以下步驟來完成：

構建後綴數組SA以及LCP的陣列（最長公共前綴數組）。後綴數組是字符串中所有後綴的字典順序列表（類似於您在示例中給出的列表，但按字典順序排序。請注意，每個後綴都由其原始字符串中的起始位置表示，即每個後綴一個整數）。 LCP也是一個整數數組，與後綴數組長度相同。在i> 0的每個位置，LCP [i]是後綴數組的第i個後綴與第（i-1）個後綴相同的最長前綴;我們設置LCP [0]：= 0。

可以使用Skew算法（也稱爲DC算法）以線性時間構造後綴數組，並且可以在O（n）時間內在後綴數組旁邊構造LCP數組。有關進一步的想法和實現，請參見SO post on state-of-the-art suffix array algorithms。
確定完整字符串在後綴數組中的位置（例如，通過線性掃描包含整數0的條目的後綴數組）。
從該位置開始沿着LCP陣列向左和向右行進，以識別每個後綴與完整字符串具有相同的最長前綴。我已在this older SO post中詳細描述了此過程。

備註雖然這需要不超過O（n）的內存和更多的時間，因此在理論上是最優的，這是一個非常複雜的過程，如果你的字符串是非常長的，只會在實踐中非常有用。

來源

2012-07-26 05:24:06 jogojapan

是啊..它似乎很複雜。我的字符串長度爲100萬。謝謝你的幫助：） – vijay 2012-07-26 07:34:31

使用後綴數組。後綴數組DC3將在O（N）時間內完成，其中N是原始字符串中的字符數。

來源

2013-03-15 05:16:02

字符串中的子串計算

回答

相關問題