甲克朗徹方案

我在寫一個程序，其中我在1甲克朗徹方案

以除去一個子字符串的所有連續重複次數在增加長度的起動次序。例如，如果字符串是「abcabeccced」。除去長度爲1的重複子串後：「abcababceccced」 - > 「abcababceced」（2 'C' 被移除）除去長度爲2的重複子串後：「abcababceced」 - > 「abcabceced」（子「ab」被刪除）等等......

有人可以爲此提出一個高效的代碼，甚至是一個想法如何做到這一點？

來源

2012-01-21 Aiden

它應該是大於兩個環路/ O（N * N）更有效率？ – wildplasser

這是功課嗎？ –

其實沒有這樣的restriction.But我正在尋找具有高efficiency.I一個簡單的邏輯找到了一個解決方案，在http://ds-gyan.blogspot.com/2010/01/string-cruncher.html但找更好的方法。 – Aiden

這是未經測試的僞代碼，但你希望做這樣的事情：

void crunch(char *str) 
{ 
    for (n=1; n<10; n++) 
    { 
    ptr = str; 
    while (*ptr != '\0') 
    { 
     while (strncmp(ptr, ptr + n, n) == 0) 
     strcpy(ptr, ptr + n); 
     ptr++; 
    } 
    } 
}

它可以優化更好，但是，我選擇優化的僞代碼跨越的想法。這段代碼的問題是：

這是低效的，因爲它使用的strcpy（一個SRC，DST指針一雙會更好）
在PTR環路一直到字符串的結尾，我們可以放棄前面
那裏面有，這個可以推廣
此功能重寫存儲器由乙方指出的10的硬編碼限制，而副本可能會更好
（編輯）更改內，如果到內，同時以「緊縮'重複序列。

來源

2012-01-21 13:14:53

這是關於我想到的兩個循環。注意：你可以用for（）循環替換外部的while（）循環，這可能更具可讀性。我認爲你需要memmove（），因爲字符串重疊（儘管指針不是）。 src/dst對可以避免這種情況。 – wildplasser

@wildplasser yeah memmove（）比strcpy（）更優化，但它需要你知道要複製的字節的長度。我知道你有辦法以有效的方式做到這一點。但是，在這種情況下，我選擇strcpy（），因爲這意味着我可以依賴NUL終結符，並且它使得僞代碼簡潔。 –

您可以直接從定義程序這一點：

input s : string 
for len between 0 and s.Length/2 
    for pos between 0 and s.Length - len 
     sub = s.substring(from pos to pos + len) 
     subSub = sub + sub 
     while (s.Contains(subSub)) 
      s = s.ReplaceAll(subSub, sub)

算法設法加倍長度LEN的所有子串，並與單打取代一倍字符串。

來源

2012-01-21 13:15:34 dasblinkenlight

您的算法可能不會將三倍字符串替換爲三倍'c'樣本被揉成單個'c'的單一值。 –

@BicycleDude你說得對，我加了一個'while'循環來解決這個問題。 – dasblinkenlight

甲克朗徹方案

回答

相關問題