C++ 程序生成长度为 n 的 Lyndon Words

在本文中，我们将讨论一个用于生成长度为 n 的 Lyndon 词的 C++ 程序。在进行实现之前，我们必须了解 Lyndon 词。

什么是 Lyndon 词？

Lyndon 词是非空字符串，其特点是按字典序小于其任何非平凡旋转。换句话说，Lyndon 词是小于其任何旋转（不包括其自身）的字符串。Lyndon 词因其此特性在字符串理论和组合学中至关重要。由于其独特的分解特性，它们对于算法、密码学、生物信息学和数据压缩的研究很重要。

示例-1

输入

S[] = {0, 1} 且 n = 4

输出

0001

0011

0111

示例-2

考虑整数集 {1,2,3}。

步骤-1：生成所有长度为 1 的可能词

1,2,3

步骤-2：生成所有长度为 2 的可能词

11,12,13,22,23,33

步骤-3：生成所有长度为 3 的可能词

• 以 1 开头，附加 1,2,3 得到 111,112,113。
• 以 2 开头，附加 2,3 得到 222,223。
• 以 3 开头，附加 3 得到 333。
• 由于长度已固定为 3，无需考虑进一步扩展。

结果

以下是从数字 {1,2,3} 生成的长度为 3 的 Lyndon 词

111,112,113,222,223,333

算法

步骤-1：使用 sort() 方法将字符数组按非递减顺序排列。

步骤-2：初始化一个名为“ch”的向量，用于存储数组中的字符索引。

步骤-3：通过将“-1”推入“ch”向量来表示初始索引。

步骤-4：利用 while 循环，迭代“ch”向量直到其大小大于零。

步骤-5：将“ch”向量中的最后一个索引增加 1。

步骤-6：将“ch”向量的长度存储在“ch_size”变量中。

步骤-7：如果“ch_size”等于“1”，则打印与“ch”向量中的索引对应的字符，以生成长度为“l”的 Lyndon 词。

步骤-8：重复将字符从“ch”向量本身附加到“ch”向量，直到“ch”向量的大小小于“l”。

步骤-9：如果“ch”向量的大小大于零且“ch”向量中的最后一个字符索引等于数组的最后一个索引，则将其从“ch”向量中删除。

示例

让我们举一个例子来生成 C++ 中长度的 Lyndon 词。

输出

 
Please enter the length of the Lyndon words: 2
Please enter the length of the characters array: 3
Enter the characters separated by space: 0 1 2
The Lyndon words of length 2 are: 
01
02
12   

说明

这个C++程序使用给定的字符数组 (C) 和特定长度 (arr_len) 来生成特定长度 (num_ber) 的 Lyndon 词。数组中的字符被排序，初始化一个向量来存储索引 (ch)，并迭代所有可能的索引组合以生成词。当生成的词的大小与所需长度匹配时，它通过使用索引连接数组中的字符来创建词并打印结果。程序读取由空格分隔的字符，要求用户输入 Lyndon 词的长度和字符数组，然后执行 GeneratingLydonWords 函数，并提供输入以生成和打印 Lyndon 词。

复杂度分析

• 时间复杂度 - O(N*logN)
  O(N* logN) 是时间复杂度，因为需要对数组进行排序。
• 空间复杂度 − O(N)
  “ch”数组用于存储元素的索引，导致空间复杂度为 O(N)。