資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
