最小循环移位算法解释

Question

我最近反对这个没有任何评论的代码.它找到了字的最小循环移位(此代码专门返回其在字符串中的索引)和它的称为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;
}

Answer 1

首先，我相信你的代码有一个错误。最后一行应该是 return p;. 我相信 i 保存字典顺序最小循环移位的索引，而 p 保存匹配的最小移位。我还认为你的停止条件太弱，即在找到匹配项后你做了太多检查，但我不确定它应该是什么。

请注意，i 和 j 只前进，并且 i 始终小于 j。我们正在寻找一个与从 i 开始的字符串相匹配的字符串，并且我们正在尝试将它与从 j 开始的字符串相匹配。我们通过比较每个字符串的第 k 个字符同时增加 k（只要它们匹配）来实现此目的。请注意，只有当我们确定从 j 开始的字符串按字典顺序小于从 j 开始的字符串时，我们才会更改 i，然后将 i 设置为 j 并将 k 和 p 重置为其初始值。

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

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，我们就会在下一个假设出现的字符串处开始再次扫描。

进一步编辑以尝试回答杰思罗的问题。

首先：k != pinelse if (a==b && k!=p) 这里我们有一个匹配，因为从 i 和 j 开始的字符串中的第 k 个字符和所有前面的字符都相等。变量 p 表示我们认为重复字符串的长度。k != p实际上，当k < p时，我们确保从 i 开始的字符串中的 p 个字符与从 j 开始的字符串中的 p 个字符相同。当k == p（最后的 else）我们应该处于从 开始的字符串看起来j + k与从 j 开始的字符串相同的点时，因此我们将 j 增加 p 并将 k 设置回 1，然后返回比较两个字符串。

第二：是的，我相信你是对的，它应该返回i。我误解了“最小循环移位”的含义