最小循环移位算法说明
我最近提出这个代码缺乏评论。 它发现字的最小循环移位（该代码具体返回字符串中的索引）和其称为Duval算法。 只有我发现的信息用几个字来描述算法，并且代码更简洁。 我将不胜感激任何帮助理解这种算法。 我总是发现文本算法非常棘手，而且很难理解。
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;
}
首先，我认为你的代码有一个bug。 最后一行应该是return p; 。 我认为我拥有词典上最小的循环移位索引，并且p保持匹配的最小移位。 我也认为你的阻挡条件太弱，即你在找到一场比赛后做了太多的检查，但我不确定它应该是什么。
请注意，我和j只会前进，而我总是小于j。 我们正在寻找一个匹配从i开始的字符串的字符串，并且我们试图将它与从j开始的字符串进行匹配。 我们通过比较每个字符串的第k个字符，同时增加k（只要它们匹配）来做到这一点。 请注意，如果我们确定从j开始的字符串在字典顺序上小于从j开始的字符串，则我们只更改i，然后将i设置为j并将k和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的问题。
首先：在else if (a==b && k!=p) ， k != p else if (a==b && k!=p)在这里我们有一个匹配，因为从第i个和第j个开始的字符串中的第k个和之前的所有字符是相等的。 变量p表示我们认为重复字符串的长度。 当k != p ，实际上k < p ，所以我们确保从i开始的字符串处的p个字符与从j开始的字符串的p个字符相同。 当k == p （final else）时，我们应该在从j + k开始的字符串看起来与从j开始的字符串相同的点上，所以我们将p增加到p并将k设回1并返回到比较两个字符串。
第二：是的，我相信你是正确的，它应该返回我。 我误解了“最小循环移位”的含义
它可能与这个算法相同，其解释可以在这里找到：
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;
}