Dado un entero n y una array de caracteres S , la tarea es generar palabras Lyndon de longitud n que tengan caracteres de S .
Una palabra de Lyndon es una string que es estrictamente menor que todas sus rotaciones en orden lexicográfico. Por ejemplo, la string “012” es una palabra Lyndon ya que es menor que sus rotaciones “120” y “201”, pero “102” no es una palabra Lyndon ya que es mayor que su rotación “021”. Nota: “000” no se considera una palabra Lyndon ya que es igual a la string obtenida al rotarla.
Ejemplos:
Entrada: n = 2, S = {0, 1, 2} Salida: 01 02 12 Otras posibles strings de longitud 2 son «00», «11», «20», «21» y «22». Todos estos son mayores o iguales a una de sus rotaciones. Entrada: n = 1, S = {0, 1, 2} Salida: 0 1 2
Enfoque: existe un enfoque eficiente para generar palabras de Lyndon que fue proporcionado por Jean-Pierre Duval, que se puede usar para generar todas las palabras de Lyndon hasta una longitud n en el tiempo proporcional al número de dichas palabras. (Consulte el documento » Coste promedio del algoritmo de Duval para generar palabras de Lyndon » de Berstel et al. para ver la prueba) El algoritmo genera las palabras de Lyndon en un orden lexicográfico. Si w es una palabra de Lyndon, la siguiente palabra se obtiene mediante los siguientes pasos:
- Repita w para formar una string v de longitud n , tal que v[i] = w[i mod |w|] .
- Si bien el último carácter de v es el último en el orden ordenado de S , elimínelo.
- Reemplace el último carácter de v por su sucesor en el orden ordenado de S.
Por ejemplo, si n = 5, S = {a, b, c, d} y w = «sumar», entonces obtenemos v = «sumar». Dado que ‘d’ es el último carácter en el orden ordenado de S, lo eliminamos para obtener «adda» y luego reemplazamos la última ‘a’ por su sucesora ‘b’ para obtener la palabra Lyndon «addb».
A continuación se muestra la implementación del enfoque anterior:
C++
// 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 is not empty
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
Java
// Java program to check if a string is two time
// rotation of another string.
import java.util.*;
public class Main
{
// Driver method
public static void main(String[] args)
{
int n=2;
char S[]={'0', '1', '2' };
int k = 3;
Arrays.sort(S);
// To store the indices
// of the characters
ArrayList<Integer> w = new ArrayList<Integer>();
w.add(-1);
// Loop till w is not empty
while(w.size() > 0)
{
// Incrementing the last character
Integer value = w.get(w.size()-1); // get value
value = value + 1; // increment value
w.set(w.size()-1, value); // replace value
int m = w.size();
if(m == n)
{
String str="";
for(int i = 0; i < w.size(); i++)
{
value = w.get(i);
str += S[value];
}
System.out.println(str);
}
// Repeating w to get a
// n-length string
while(w.size() < n)
{
value = w.size() - m;
value = w.get(value);
w.add(value);
}
// Removing the last character
// as long it is equal to
// the largest character in S
while(w.size() > 0 && w.get(w.size() - 1) == k - 1)
{
w.remove(w.size()-1);
}
}
}
}
// This code is contributed by Aarti_Rathi
Python3
# Python implementation of
# the above approach
n = 2
S = ['0', '1', '2']
k = len(S)
S.sort()
# To store the indices
# of the characters
w = [-1]
# Loop till w is not empty
while w:
# Incrementing the last character
w[-1] += 1
m = len(w)
if m == n:
print(''.join(S[i] for i in w))
# Repeating w to get a
# n-length string
while len(w) < n:
w.append(w[-m])
# Removing the last character
# as long it is equal to
# the largest character in S
while w and w[-1] == k - 1:
w.pop()
C#
using System;
using System.Collections.Generic;
class GFG
{
// Driver code
public static void Main ()
{
int n=2;
char [] S={'0', '1', '2' };
int k = 3;
Array.Sort(S);
// To store the indices
// of the characters
List<int> w = new List<int>();
w.Add(-1);
// Loop till w is not empty
while(w.Count > 0)
{
// Incrementing the last character
w[w.Count-1]++;
int m = w.Count;
if(m == n)
{
string str="";
for(int i = 0; i < w.Count; i++)
{
str += S[w[i]];
}
Console.WriteLine(str);
}
// Repeating w to get a
// n-length string
while(w.Count < n)
{
w.Add(w[w.Count - m]);
}
// Removing the last character
// as long it is equal to
// the largest character in S
while(w.Count > 0 && w[w.Count - 1] == k - 1)
{
w.RemoveAt(w.Count-1);
}
}
}
}
// This code is contributed by Aarti_Rathi
Javascript
<script>
// JavaScript implementation of
// the above approach
// driver code
let n = 2;
let S = ['0', '1', '2'];
let k = 3;
S.sort();
// To store the indices
// of the characters
let w = [];
w.push(-1);
// Loop till w is not empty
while(w.length > 0)
{
// Incrementing the last character
w[w.length-1]++;
let m = w.length;
if(m == n)
{
let str = "";
for(let i = 0; i < w.length; i++)
{
str += S[w[i]];
}
document.write(str,"</br>");
}
// Repeating w to get a
// n-length string
while(w.length < n)
{
w.push(w[w.length - m]);
}
// Removing the last character
// as long it is equal to
// the largest character in S
while(w.length > 0 && w[w.length - 1] == k - 1)
{
w.pop();
}
}
// This code is contributed by shinjanpatra
</script>
01 02 12
Publicación traducida automáticamente
Artículo escrito por vaibhav29498 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA