用于生成长度为 n 的 Lyndon 单词的 C++ 程序
在此问题中，我们需要使用给定的字符生成长度为 n 的 Lyndon 单词。Lyndon 单词是这样的单词:其任何旋转都严格大于其本身的字典顺序。
以下是 Lyndon 单词的示例。
01 − '01' 的旋转为 '10'，始终严格大于 '01'。
012 − '012' 的旋转为 '120' 和 '210'，严格大于 '012'。
问题陈述 − 我们给出了一个包含数字字符的数组 s[]。另外，我们给出了 n 来表示 Lyndon 单词的长度。我们需要使用数组字符生成长度为 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);
// 用于存储索引
vector<int> chars;
// 初始索引为 -1
chars.push_back(-1);
// 进行迭代，直到 chars 的大小大于 0
while (chars.size() > 0) {
// 将最后一个字符增加 1
chars[chars.size() - 1]++;
// 存储数组的大小
int chars_size = chars.size();
// 如果大小等于 len，则我们找到了 Lyndon 单词
if (chars_size == len) {
// 打印单词
string temp;
for (int p = 0; p < chars.size(); p++) {
temp += characters[chars[p]];
}
cout << temp << endl;
}
// 继续添加字符，直到其长度等于 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 << "长度为 2 的 Lyndon 单词为 :- \n ";
generateLydonWord(S, array_len, n);
return 0;
}
输出
长度为 2 的 Lyndon 单词为:- 01 02 12
时间复杂度− O(N* logN)，因为我们需要对数组进行排序。
空间复杂度− O(N)，因为我们使用"chars"数组来存储元素的索引。
我们学会了使用 Duval 算法来查找给定长度的 Lyndon 单词。此外，我们还调试了示例输入以了解 Duval 算法的工作原理。
