数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++生成长度为n的Lyndon词的程序
在这个问题中，我们需要使用给定的字符生成长度为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的Lyndon词“01”。
在接下来的迭代中，我们增加列表的最后一个索引，它变为[0, 2]。我们再次找到一个新的Lyndon词“02”。此外，在“chars”列表中，最后一个索引元素等于“array_len - 1”，因此将其删除，更新后的列表为[0]。
在接下来的迭代中，最后一个索引和更新后的列表将是[1]。将列表大小设置为2，更新后的列表将是[1, 1]。
在接下来的迭代中，将最后一个元素加1；更新后的列表将是[1, 2]。在这里，我们找到了第三个Lyndon词“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算法的工作原理。
72 次浏览
