在 O(n) 中查找字符串的所有循环排列

Question

给定问题：找出字符串的所有循环排列

例如：给定一个字符串：“abcd”

一个字符串的所有循环排列都是：“abcd”、“dabc”、“cdab”、“bcda”

这是我尝试过的：

for(int i = 0; i < str.size(); i++){
    permu.push_back(str);
    str.insert(0, 1, str[str.size()-1]);
    str.erase(str.end()-1);
}

因为插入和擦除函数需要 O(n) 使得整体解决方案 O(n^2)

有没有办法在 O(n) 或更短的时间内解决这个问题？

Answer 1

您可以使用 string_view 在 O(n) 中完成：

std::vector<std::string_view> get_perms(std::string& str) {
    auto orig_length = str.length();
    str += str;
    std::vector<std::string_view> ret;

    std::string_view sv{str};
    for (int i = 0; i < orig_length; i++) {
        auto sv2 = sv.substr(i, orig_length);
        ret.push_back(sv2);
    }
    return ret;
}

获取 string_view 的子串是常数时间，但您需要确保原始 string 保持活动状态。这就是函数将 str 作为非常量引用的原因。

Answer 2

如果您不想创建另一个字符串，还有另一种方法：

for(int i = 0; i < str.size(); i++)
    permu.push_back(str.substr(i) + str.substr(0, i));

在 O(n) 中查找字符串的所有循环排列

Find all cyclic permutations of a string in O(n)

c++

permutation

circular-permutations