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

给定一个整数 n 和一个包含字符的数组 S，任务是生成长度为 n 的 Lyndon 词，它的字符来自 S。

Lyndon 词是一个严格小于其所有旋转的词的字符串。例如，字符串“012”是一个 Lyndon 词，因为它小于其旋转“120”和“201”，但是“102”不是 Lyndon 词，因为它大于其旋转“021”。

注意： “000”不被视为 Lyndon 词，因为它等于其旋转获得的字符串。

示例：

输入： n = 2, S = {0, 1, 2}

输出： 01

长度为 2 的其他可能字符串为 “00”、”11″、”20″、”21″ 和 “22”。所有这些字符串要么大于等于它们的旋转，要么大于等于它们的旋转。

输入： n = 1, S = {0, 1, 2}

输出： 0

方法： 存在一种有效的方法来生成 Lyndon 词，即由 Jean-Pierre Duval 给出的方法，可以使用该方法按比例生成长度为 n 的所有 Lyndon 词与这样的单词的数量时间。（请参阅 Berstel et al. 的论文“生成 Lyndon 词的 Duval 算法的平均成本”进行证明）。

该算法以字典顺序生成 Lyndon 词。如果 w 是一个 Lyndon 词，则下一个词通过以下步骤获得：

重复 w，以形成长度为 n 的字符串 v，使得 v[i] = w[i mod |w|]。
当 v 的最后一个字符是 S 的排序中的最后一个字符时，将其删除。
用 S 的排序中的其继承者替换 v 的最后一个字符。

例如，如果 n = 5，S = {a，b，c，d}，并且 w = “add”，则我们得到 v = “addad”。

由于“d”是S的排序中的最后一个字符，因此我们删除它以获得“adda”

然后将最后一个“a”替换为其后继“b”，以获得 Lyndon 词“addb”。

下面是上述方法的实现：

// C++ implementation of 
// the above approach 
#include<bits/stdc++.h>
using namespace std;
  
int main()
{
    int n = 2;
    char S[] = {'0', '1', '2' };
    int k = 3;
    sort(S, S + 3);
      
    // To store the indices 
    // of the characters 
    vector<int> w;
    w.push_back(-1);
      
    // Loop till w不为空     
    while(w.size() > 0)
    {
          
        // Incrementing the last character
        w[w.size()-1]++;
        int m = w.size();
        if(m == n)
        {
            string str;
            for(int i = 0; i < w.size(); i++)
            {
                str += S[w[i]];
            }
            cout << str << endl;
        }
      
        // Repeating w to get a 
        // n-length string
        while(w.size() < n)
        {
            w.push_back(w[w.size() - m]);
        }
      
        // Removing the last character 
        // as long it is equal to 
        // the largest character in S 
        while(w.size() > 0 && w[w.size() - 1] == k - 1)
        {
            w.pop_back();
        }
    }
    return 0;
}
  
// This code is contributed by AdeshSingh1