最小循環移位算法解釋

Question

我最近提出這個代碼缺乏任何評論。它發現字的最小循環移位（該代碼具體返回字符串中的索引）和其稱爲Duval算法。只有info我發現用幾個字描述算法並且代碼更簡潔。我將不勝感激任何幫助理解這種算法。我總是發現文本算法非常棘手，而且很難理解。

int minLexCyc(const char *x) { 
    int i = 0, j = 1, k = 1, p = 1, a, b, l = strlen(x); 
    while(j+k <= (l<<1)) { 
     if ((a=x[(i+k-1)%l])>(b=x[(j+k-1)%l])) { 
      i=j++; 
      k=p=1; 
     } else if (a<b) { 
      j+=k; 
      k=1; 
      p=j-i; 
     } else if (a==b && k!=p) { 
      k++; 
     } else { 
      j+=p; 
      k=1; 
     } 
    } 
    return i; 
} 

Answer 1

首先，我相信你的代碼有一個bug。最後一行應該是 return p;。我認爲我擁有詞典上最小的循環移位索引，並且p保持匹配的最小移位。我也認爲你的停賽條件太弱，即在你找到一場比賽後你做了太多的檢查，但我不確定它應該是什麼。

請注意，我和j只會前進，而我總是小於j。我們正在尋找一個匹配從i開始的字符串的字符串，並且我們試圖將它與從j開始的字符串進行匹配。我們通過比較每個字符串的第k個字符，同時增加k（只要它們匹配）來做到這一點。請注意，如果我們確定從j開始的字符串在字典順序上小於從j開始的字符串，則我們只更改i，然後將i設置爲j並將k和p重置爲它們的初始值。

我沒有時間進行了詳細的分析，但它看起來像

1. I =的字典最小的循環移位
2. J =我們是匹配的對循環移位開始的開始轉移起始於我
3. K =在字符串中的字符i和所考慮目前Ĵ（在位置1中的字符串匹配到k-1
4. p =所考慮的循環移位（我相信p爲前綴）

編輯進一步

走出去的代碼

if ((a=x[(i+k-1)%l])>(b=x[(j+k-1)%l])) { 
     i=j++; 
     k=p=1; 

本節，當我們發現一個，並重新初始化一切與移動相比於早期的字典序字符串的開始。

本條

} else if (a<b) { 
     j+=k; 
     k=1; 
     p=j-i; 

是棘手的部分。我們發現按照字典順序排列的時間比我們的引用字符串更不匹配，所以我們跳到目前匹配的文本的末尾，並從那裏開始匹配。我們也增加p（我們的步伐）。爲什麼我們可以跳過j和j + k之間的所有起點？這是因爲從i開始的字符串是字典中最小的字符串，如果當前j字符串的尾部大於i的字符串，那麼j處字符串的任何後綴都將大於i處的字符串。

最後

} else if (a==b && k!=p) { 
     k++; 
    } else { 
     j+=p; 
     k=1; 

這僅僅檢查開始於我重複長度p的字符串。

**進一步編輯* 我們通過遞增k直到k == p，檢查從i開始的字符串的第k個字符等於從j開始的字符串的第k個字符。一旦k達到p，我們在下一次假定的字符串出現時再次開始掃描。

甚至進一步編輯試圖回答jethro的問題。

第一個：k != p在else if (a==b && k!=p)這裏我們有一個匹配，第k個字符和從i和j開始的所有以前的字符都是相等的。變量p表示我們認爲重複字符串的長度。當k != p，實際上k < p，所以我們確保從i開始的字符串處的p字符與從j開始的字符串的p字符相同。當k == p（最後的else）時，我們應該在從j + k開始的字符串看起來與從j開始的字符串相同的點上，因此我們將p增加到p並將k置回1並返回比較兩個字符串。

第二：是的，我相信你是正確的，它應該返回我。我被誤解「最小循環移位」

Answer 2

這可能是與此相同的算法，它的解釋可以發現here的含義：

int ComputeMaxSufPos(string w) 
{ 
    int i = 0, n = w.Length; 
    for (int j = 1; j < n; ++j) 
    { 
     int c, k = 0; 
     while ((c = w[(i + k) % n].CompareTo(w[(j + k) % n])) == 0 && k != n) 
     { k++; } 
     j += c > 0 ? k/(j - i) * (j - i) : k; 
     i = c > 0 ? j : i; 
    } 
    return i; 
}