最小循环移位算法解释

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

首先，我相信你的代码中有一个错误。最后一行应该是return p;。我认为我保持了按字典顺序排列的最小循环移位的索引，并且p保持匹配的最小移位。我也认为你的停止条件太弱，即你在找到比赛后做了太多的检查，但我不确定应该是什么。

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

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

1. i =词典最小循环移位的开始
2. j =循环移位的开始，我们匹配从i开始的移位
3. k =当前正在考虑的字符串i和j中的字符（字符串在位置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;

这只是检查从i开始的长度为p的字符串重复。

**进一步编辑*我们通过将k递增到k == p来执行此操作，检查从i开始的字符串的第k个字符是否等于从j开始的字符串的第k个字符。一旦k到达p，我们就会在下一个假定的字符串出现时再次开始扫描。

甚至进一步编辑试图回答jethro的问题。

首先：k != p中的else if (a==b && k!=p)这里我们有一个匹配，因为从i和j开始的字符串中的第k个和所有先前字符是相等的。变量p表示我们认为重复字符串的长度。当k != p，实际上是k < p，所以我们确保从i开始的字符串中的p字符与从j开始的字符串的p字符相同。当k == p（最后的其他）我们应该处于从j + k开始的字符串看起来与从j开始的字符串相同的点时，所以我们将j增加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;
}