C++ 生成长度为 n 的 Lyndon 单词

在这个问题中，我们需要使用给定的字符生成长度为 n 的 Lyndon 单词。Lyndon 单词是这样的单词，它的任意一个旋转在字典序中都严格大于它自己。

以下是 Lyndon 单词的示例。

• 01 − ‘01’ 的旋转是 ‘10’，它始终严格大于‘01’。

• 012 − ‘012’ 的旋转是 ‘120’ 和 ‘210’，它们严格大于 ‘012’。

问题陈述 − 我们已经给出了一个包含数字字符的数组 s[]。同时，我们给出了表示 Lyndon 单词长度的 n。我们需要使用数组字符生成长度为 n 的 Lyndon 单词。

示例

输入

S[] = {'0', '1', '2'}, n = 2

输出

01, 02, 12

解释 - 我们使用字符’0’、’1’和’2’生成了长度为2的Lyndon词。

示例

输入

S[] = {'0', '1'}, n = 3

输出

001, 011

解释 - ‘001’ 和 ‘011’ 的所有旋转都按字典顺序大于其本身。

方法1

我们可以使用Duval算法生成Lyndon单词。程序员可以按照以下算法使用数组的字符生成长度为n的Lyndon单词。

步骤

步骤 1 - 使用sort()方法对字符数组进行排序。

步骤 2 - 定义一个‘chars’向量来存储字符数组的索引。

步骤 3 - 最初将‘-1’推入‘chars’列表，表示起始索引。

步骤 4 - 使用while循环进行迭代，直到‘chars’列表的大小大于零。

步骤 5 - 将最后一个索引增加1。

步骤 6 - 将列表大小存储在‘chars_size’变量中。

步骤 7 - 如果‘chars_size’等于‘len’，则找到长度等于‘len’的Lyndon单词。打印‘chars’列表的所有字符。

步骤 8 - 使用循环将字符添加到‘chars’列表，直到列表的长度小于‘len’。我们可以从‘chars’列表获取字符，并将它们追加到列表的末尾。

步骤 9 - 如果‘chars’列表的大小大于零且列表的最后一个字符等于数组的最后一个字符，则从列表中删除它。

示例

我们来调试下面示例的示例输入以更好地理解。

• 最初，chars列表将为[−1]。

• 第一次迭代中，chars列表将变为[0]。之后，列表的大小与len不相等，所以我们继续前进。在这里，我们创建一个大小为len的列表，更新后的列表将为[0, 0]。

• 在下一次迭代中，我们将最后一个元素增加1，使得结果列表为[0, 1]。在这次迭代中，我们的列表大小等于len，并且我们可以从第0个和第1个索引中取字符来创建长度为2的第一个Lydon单词，即’01’。

• 在下一次迭代中，我们增加列表的最后一个索引，它变为[0, 2]。我们再次找到一个新的Lydon单词，即’02’。还有，在chars列表中，最后一个索引元素等于array_len − 1，因此将其删除，更新后的列表为[0]。

• 在下一次迭代中，最后一个索引和更新后的列表将为[1]。使列表大小等于2，更新后的列表将为[1, 1]。

• 在下一次迭代中，将最后一个元素增加1，更新后的列表将为[1, 2]。在这里，我们找到了第三个Lydon单词，即’12’。

#include <bits/stdc++.h>
using namespace std;
void generateLydonWord(char characters[], int array_len, int len) {
    sort(characters, characters + array_len);
    // for storing the indexes
    vector<int> chars;
    // Initial index is -1
    chars.push_back(-1);
    // Make iterations till the size of chars is greater than 0
    while (chars.size() > 0) {
        // Increase last char by 1
        chars[chars.size() - 1]++;
        // store the size of the array
        int chars_size = chars.size();
        // If the size is equal to len, we found the Lyndon word
        if (chars_size == len) {
            // Print the word
            string temp;
            for (int p = 0; p < chars.size(); p++) {
                temp += characters[chars[p]];
            }
            cout << temp << endl;
        }
        // keep appending the chars characters until its length becomes equal to len
        while (chars.size() < len) {
            chars.push_back(chars[chars.size() - chars_size]);
        }
        while (chars.size() > 0 && chars[chars.size() - 1] == array_len - 1) {
            chars.pop_back();
        }
    }
}
int main() {
    int n = 2;
    char S[] = {'0', '1', '2'};
    int array_len = sizeof(S) / sizeof(S[0]);
    cout << "The Lyndon words of length 2 are :- \n ";
    generateLydonWord(S, array_len, n);
    return 0;
}

输出

The Lyndon words of length 2 are :- 
 01
02
12

时间复杂度： − O(N* logN)，因为我们需要对数组进行排序。

空间复杂度： − O(N)，因为我们使用’chars’数组来存储元素的索引。

我们学习了如何使用Duval算法找到给定长度的Lyndon词。此外，我们还调试了样例输入以了解Duval算法的工作原理。