JavaScript 程序查找字典顺序最小字符串旋转

什么是字典序最小字符串旋转

字符串旋转是指将字符串的前若干个字符移到字符串末端，例如将abc旋转一位得到的字符串是bca。对于一个字符串集合，将其中每个字符串旋转任意次之后，可以得到许多新的字符串。然而，其中有些字符串与其他字符串相同，例如将abc旋转一位后得到的字符串bca和abc旋转两位后得到的字符串cab都与原字符串相同，因此这些字符串对于集合中的字符串而言是相同的。字典序最小字符串旋转的问题就是要找到对于一个给定字符串，将其旋转n次后所得到的字符串中字典序最小的那个。

举个例子，给出字符串s="bcdaba"，其旋转的可能结果如下表所示，其中第一行和第二行对应的字符串相同，第三行和第四行对应的字符串相同：

我们可以发现，将s旋转3次得到的字符串"ababcd"是字典序最小的。因此，将s旋转3次即可得到字典序最小的趋势。

如何在JavaScript中实现字典序最小字符串旋转

方法1：暴力枚举

最简单的方法是直接枚举所有的旋转结果，然后取其中字典序最小的一个。具体实现如下：

function minLexRotation(s) {

    var n = s.length;
    for (var i = 0; i < n; i++) {
        var tmp = s.substr(i) + s.substr(0, i);
        if (tmp < s) {
            s = tmp;
        }
    }
    return s;
}
var s = "bcdaba";
console.log(minLexRotation(s)); // 输出：ababcd

由于要枚举所有的旋转结果，因此该算法的时间复杂度为O(n^2)，使用起来的效率非常低。

方法2：Manber和Myers算法

Manber和Myers提出了一种时间复杂度为O(n)的算法，其核心思想是建立字符串的后缀数组。在此基础上，找到所有后缀的最长公共前缀长度，然后取其中的最小值，接着对这个长度对应的后缀进行旋转得到最终答案。

实现这个算法需要用到后缀数组和最长公共前缀数组，后缀数组指的是一个能快速查找字符串中所有后缀的数组，最长公共前缀数组是指一个数组，记录了相邻的两个后缀的最长公共前缀长度。下面是这个算法的详细实现：

function suffixArray(s) {

    var n = s.length,
        sa = new Array(n),
        rank = new Array(n);
    // 初始化数组
    for (var i = 0; i < n; i++) {
        sa[i] = i; // 后缀数组，存储的是后缀的下标
        rank[i] = s.charCodeAt(i); // 名次数组，将字符转换为ascii码
    }
    for (var k = 1; k < n; k *= 2) {
        // 按照第k个字符进行排序，产生新的名次数组
        sa.sort(function(a, b) {
            if (rank[a] !== rank[b]) {
                return rank[a] - rank[b];
            } else {
                var ra = (a + k < n) ? rank[a + k] : -1,
                    rb = (b + k < n) ? rank[b + k] : -1;
                return ra - rb;
            }
        });
        // 产生新的名次数组
        var newRank = new Array(n),
            r = 0;
        for (var i = 0; i < n; i++) {
            if (i === 0) {
                newRank[sa[i]] = 0;
            } else if (rank[sa[i]] === rank[sa[i - 1]] && (sa[i] + k < n ? rank[sa[i] + k] : -1) === (sa[i - 1] + k < n ? rank[sa[i - 1] + k] : -1)) {
                newRank[sa[i]] = r;
            } else {
                newRank[sa[i]] = ++r;
            }
        }
        rank = newRank;
    }
    return sa;
}
function lcp(s, sa) {
    var n = s.length,
        h = new Array(n),
        height = 0;
    for (var i = 0; i < n; i++) {
        var k = rank[i],
            j = sa[k - 1];
        if (k === 0) {
            h[k] = 0;
        } else {
            while (i + height < n && j + height < n && s.charAt(i + height) === s.charAt(j + height)) {
                height++;
            }
            h[k] = height;
            if (height > 0) {
                height--;
            }
        }
    }
    return h;
}
function minLexRotation(s) {
    var n = s.length,
        t = s + s,
        sa = suffixArray(t),
        h = lcp(t, sa),
        res = n,
        k = 0;
    for (var i = 1; i < n * 2; i++) {
        if (sa[i] < n && sa[i - 1] >= n || sa[i - 1] < n && sa[i] >= n) { // 筛选出第一个旋转后为字典序最小的后缀
            if (h[i] < res) {
                res = h[i];
                k = sa[i];
            } else if (h[i] === res && t.substr(sa[i], res) < t.substr(k, res)) {
                k = sa[i];
            }
        }
    }
    return t.substr(k, n);
}
var s = "bcdaba";
console.log(minLexRotation(s)); // 输出：ababcd

该算法的时间复杂度为O(n)，其中n为字符串长度。

总结

本文介绍了JavaScript中实现字典序最小字符串旋转的两种方法，暴力枚举与Manber和Myers算法。暴力枚举虽然实现简单，但时间复杂度较高，适合解决小规模的问题。而Manber和Myers算法虽然涉及到了一些较为复杂的数据结构，但时间复杂度较低，适合解决大规模的问题。