Programa C++ para encontrar la secuencia rotada lexicográficamente más pequeña | conjunto 2

Escriba código para encontrar el mínimo lexicográfico en una array circular, por ejemplo, para la array BCABDADAB, el mínimo lexicográfico es ABBCABDAD
Restricción de entrada: 1 < n < 1000 
Ejemplos: 
 

Input:  GEEKSQUIZ
Output: EEKSQUIZG

Input:  GFG
Output: FGG

Input :  CAPABCQ
Output : ABCQCAP

Hemos discutido una solución O(n 2 Logn) en Rotación lexicográficamente mínima de strings | conjunto 1 . Aquí necesitamos encontrar el índice inicial de rotación mínima y luego imprimir la rotación.
 

1) Initially assume 0 to be current min 
   starting index.
2) Loop through i = 1 to n-1.
   a) For each i compare sequence starting 
      at i with current min starting index
   b) If sequence starting at i is lexicographically 
      smaller, update current min starting 
      index.

Aquí está el pseudocódigo para el algoritmo. 
 

function findIndexForSmallestSequence(S, n):
    result = 0
    for i = 1:n-1
        if (sequence beginning at i < 
               sequence beginning at result)
            result = i
        end if
    end for
    return result

Aquí está la implementación del algoritmo anterior. 
 

C++

// C++ program to find lexicographically 
// smallest sequence with rotations. 
#include <iostream> 
using namespace std; 
  
// Function to compare lexicographically 
// two sequence with different starting 
// indexes. It returns true if sequence 
// beginning with y is lexicographically 
// greater. 
bool compareSeq(char S[], int x, int y, int n) 
{ 
    for (int i = 0; i < n; i++) { 
        if (S[x] < S[y]) 
            return false; 
        else if (S[x] > S[y]) 
            return true; 
        x = (x + 1) % n; 
        y = (y + 1) % n; 
    } 
    return true; 
} 
  
// Function to find starting index 
// of lexicographically smallest sequence 
int smallestSequence(char S[], int n) 
{ 
    int index = 0; 
    for (int i = 1; i < n; i++) 
  
        // if new sequence is smaller 
        if (compareSeq(S, index, i, n)) 
  
            // change index of current min 
            index = i; 
  
    return index; 
} 
  
// Function to print lexicographically 
// smallest sequence 
void printSmallestSequence(char S[], int n) 
{ 
    int starting_index = smallestSequence(S, n); 
    for (int i = 0; i < n; i++) 
        cout << S[(starting_index + i) % n]; 
} 
  
// driver code 
int main() 
{ 
    char S[] = "DCACBCAA"; 
    int n = 8; 
    printSmallestSequence(S, n); 
    return 0; 
} 

Producción: 
 

AADCACBC

Complejidad de tiempo: O (n ^ 2) 
Espacio auxiliar: O (1)
Consulte el artículo completo sobre la secuencia rotada lexicográficamente más pequeña | Set 2 para más detalles!

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *