最小循环移位算法解释

我最近提出这个代码缺乏任何评论。它发现字的最小循环移位（该代码具体返回字符串中的索引）和其称为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; 
}

来源

2010-08-11 jethro

这将是更容易阅读，如果它不是写在这种可怕的密集风格（将任务移出状态，每行一个声明，避免过早优化，如通过移位替换* 2）。 – starblue 2010-08-11 14:44:25

首先，我相信你的代码有一个bug。最后一行应该是 return p;。我认为我拥有词典上最小的循环移位索引，并且p保持匹配的最小移位。我也认为你的停赛条件太弱，即在你找到一场比赛后你做了太多的检查，但我不确定它应该是什么。

请注意，我和j只会前进，而我总是小于j。我们正在寻找一个匹配从i开始的字符串的字符串，并且我们试图将它与从j开始的字符串进行匹配。我们通过比较每个字符串的第k个字符，同时增加k（只要它们匹配）来做到这一点。请注意，如果我们确定从j开始的字符串在字典顺序上小于从j开始的字符串，则我们只更改i，然后将i设置为j并将k和p重置为它们的初始值。

我没有时间进行了详细的分析，但它看起来像

I =的字典最小的循环移位
J =我们是匹配的对循环移位开始的开始转移起始于我
K =在字符串中的字符i和所考虑目前Ĵ（在位置1中的字符串匹配到k-1
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并返回比较两个字符串。

第二：是的，我相信你是正确的，它应该返回我。我被误解“最小循环移位”

来源

2010-08-11 16:11:41 deinst

+1：似乎有帮助:-)也许你还应该提到k> 1的情况（我相信i和j中的子串恰好匹配前k个位置）。 – 2010-08-11 16:51:59

我认为这是不必要的，但是，嘿，这是什么，我需要学会更清楚。 – deinst 2010-08-11 16:59:32

非常感谢您的时间和解释。你为什么认为最后的声明应该返回p？我们正在寻找循环移位，所以恕我直言，我是正确的。我仍然不明白我们用p是什么（例如为什么我们检查最后一个else if（k！= p）？ – jethro 2010-08-12 21:28:39

这可能是与此相同的算法，它的解释可以发现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; 
}

来源

2013-12-13 02:16:48 Mehrdad

最小循环移位算法解释

回答

相关问题