Programa C++ para rotaciones mínimas requeridas para obtener la misma string

Dada una string, necesitamos encontrar el número mínimo de rotaciones requeridas para obtener la misma string.

Ejemplos:

Input : s = "geeks"
Output : 5

Input : s = "aaaa"
Output : 1

La idea se basa en la siguiente publicación.

Un programa para verificar si las strings son rotaciones entre sí o no.

Paso 1: Inicialice el resultado = 0 (Aquí el resultado es el conteo de rotaciones)
Paso 2: Tome una string temporal igual a la string original concatenada consigo misma.
Paso 3: ahora tome la substring de la string temporal del mismo tamaño que la string original a partir del segundo carácter (o índice 1).
Paso 4: Aumente el conteo.
Paso 5: compruebe si la substring se vuelve igual a la string original. Si es así, entonces rompa el bucle. De lo contrario, vaya al paso 2 y repítalo desde el siguiente índice.

// C++ program to determine minimum number
// of rotations required to yield same
// string.
#include <iostream>
using namespace std;
  
// Returns count of rotations to get the
// same string back.
int findRotations(string str)
{
    // tmp is the concatenated string.
    string tmp = str + str;
    int n = str.length();
  
    for (int i = 1; i <= n; i++) {
  
        // substring from i index of original
        // string size.
        string substring = tmp.substr(i, str.size());
  
        // if substring matches with original string
        // then we will come out of the loop.
        if (str == substring)
            return i;
    }
    return n;
}
  
// Driver code
int main()
{
    string str = "abc";
    cout << findRotations(str) << endl;
    return 0;
}

Producción:

3

Complejidad de tiempo: O(n ² )

Consulte el artículo completo sobre Rotaciones mínimas requeridas para obtener la misma string para obtener más detalles.