Rotaciones mínimas requeridas para obtener la misma String | Conjunto-2

Dada una string, necesitamos encontrar el número mínimo de rotaciones requeridas para obtener la misma string. En este caso, solo consideraremos las rotaciones a la izquierda.

Ejemplos: 

Entrada: s = «geeks» 
Salida: 5

Entrada: s = “aaaa” 
Salida: 1 

Enfoque ingenuo: el enfoque básico es seguir girando la cuerda desde la primera posición y contar el número de rotaciones hasta que obtengamos la cuerda inicial.

Enfoque eficiente: Seguiremos el enfoque básico pero intentaremos reducir el tiempo necesario para generar rotaciones.
La idea es la siguiente:  

• Genere una nueva string del doble del tamaño de la string de entrada como:

newString = original string excluding first character 
            + original string with the first character.

+ denotes concatenation here.  

• Si la string original es str = “abcd”, la nueva string será “bcdabcd”.
• Ahora, queda la tarea de buscar la string original en la string recién generada y el índice donde se encuentra la string en el número de rotaciones requeridas.
• Para la coincidencia de strings, utilizaremos el algoritmo KMP que realiza la coincidencia de strings en tiempo lineal.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
void computeLPSArray(char* pat, int M, int* lps);
  
// Prints occurrences of txt[] in pat[]
int KMPSearch(char* pat, char* txt)
{
    int M = strlen(pat);
    int N = strlen(txt);
  
    // Create lps[] that will hold the longest
    // prefix suffix values for pattern
    int lps[M];
  
    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);
  
    // Index for txt[] , // index for pat[]
    int i = 0;
    int j = 0;
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
  
        if (j == M) {
            return i - j;
            j = lps[j - 1];
        }
  
        // Mismatch after j matches
        else if (i < N && pat[j] != txt[i]) {
 
            // Do not match lps[0..lps[j-1]] characters,
            // they will match anyway
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
}
  
// Fills lps[] for given pattern pat[0..M-1]
void computeLPSArray(char* pat, int M, int* lps)
{
    // Length of the previous longest prefix suffix
    int len = 0;
     
    // lps[0] is always 0
    lps[0] = 0;
  
    // The loop calculates lps[i] for i = 1 to M-1
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        }
 
        // (pat[i] != pat[len])
        else
        {
            // This is tricky. Consider the example.
            // AAACAAAA and i = 7. The idea is similar
            // to search step.
            if (len != 0) {
                len = lps[len - 1];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}
 
// Returns count of rotations to get the
// same string back
int countRotations(string s)
{
    // Form a string excluding the first character
    // and concatenating the string at the end
    string s1 = s.substr(1, s.size() - 1) + s;
  
    // Convert the string to character array
    char pat[s.length()], text[s1.length()];
  
    strcpy(pat, s.c_str());
    strcpy(text, s1.c_str());
  
    // Use the KMP search algorithm
    // to find it in O(N) time
    return 1 + KMPSearch(pat, text);
}
  
// Driver code
int main()
{
    string s1 = "geeks";
  
    cout << countRotations(s1);
  
    return 0;
}

// Java implementation of the above approach
class GFG
{
 
// Prints occurrences of txt[] in pat[]
static int KMPSearch(char []pat, char []txt)
{
    int M = pat.length;
    int N = txt.length;
  
    // Create lps[] that will hold the longest
    // prefix suffix values for pattern
    int lps[] = new int[M];
  
    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);
  
    // Index for txt[] , // index for pat[]
    int i = 0;
    int j = 0;
    while (i < N)
    {
        if (pat[j] == txt[i])
        {
            j++;
            i++;
        }
  
        if (j == M)
        {
            return i - j + 1;
            //j = lps[j - 1];
        }
  
        // Mismatch after j matches
        else if (i < N && pat[j] != txt[i])
        {
 
            // Do not match lps[0..lps[j-1]] characters,
            // they will match anyway
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
    return 0;
}
  
// Fills lps[] for given pattern pat[0..M-1]
static void computeLPSArray(char []pat, int M, int []lps)
{
   
    // Length of the previous longest prefix suffix
    int len = 0;
     
    // lps[0] is always 0
    lps[0] = 0;
  
    // The loop calculates lps[i] for i = 1 to M-1
    int i = 1;
    while (i < M)
    {
        if (pat[i] == pat[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
 
        // (pat[i] != pat[len])
        else
        {
            // This is tricky. Consider the example.
            // AAACAAAA and i = 7. The idea is similar
            // to search step.
            if (len != 0) {
                len = lps[len - 1];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}
 
// Returns count of rotations to get the
// same String back
static int countRotations(String s)
{
    // Form a String excluding the first character
    // and concatenating the String at the end
    String s1 = s.substring(1, s.length() - 1) + s;
  
    // Convert the String to character array
    char []pat = s.toCharArray();
    char []text = s1.toCharArray();
  
    // Use the KMP search algorithm
    // to find it in O(N) time
    return 1 + KMPSearch(pat, text);
}
  
// Driver code
public static void main(String []args)
{
    String s1 = "geeks";
    System.out.print(countRotations(s1));
}
}
 
// This code is contributed by rutvik_56.

# Python3 implementation of the above approach
 
# Prints occurrences of txt[] in pat[]
def KMPSearch(pat, txt):
 
    M = len(pat)
    N = len(txt)
 
    # Create lps[] that will hold the longest
    # prefix suffix values for pattern
    lps = [0] * M
 
    # Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps)
 
    # Index for txt[] , # index for pat[]
    i = 0
    j = 0
    while i < N:
        if pat[j] == txt[i]:
            j += 1
            i += 1
 
        if j == M:
            return i - j
            j = lps[j - 1]
 
        # Mismatch after j matches
        elif i < N and pat[j] != txt[i]:
 
            # Do not match lps[0..lps[j-1]] characters,
            # they will match anyway
            if j != 0:
                j = lps[j - 1]
            else:
                i = i + 1
 
# Fills lps[] for given pattern pat[0..M-1]
def computeLPSArray(pat, M, lps):
     
    # Length of the previous longest prefix suffix
    _len = 0
     
    # lps[0] is always 0
    lps[0] = 0
 
    # The loop calculates lps[i] for i = 1 to M-1
    i = 1
    while i < M:
        if pat[i] == pat[_len]:
            _len += 1
            lps[i] = _len
            i += 1
 
        # (pat[i] != pat[_len])
        else:
         
            # This is tricky. Consider the example.
            # AAACAAAA and i = 7. The idea is similar
            # to search step.
            if _len != 0:
                _len = lps[_len - 1]
            else:
                lps[i] = 0
                i += 1
 
# Returns count of rotations to get the
# same string back
def countRotations(s):
 
    # Form a string excluding the first character
    # and concatenating the string at the end
    s1 = s[1 : len(s)] + s
 
    # Convert the string to character array
    pat = s[:]
    text = s1[:]
 
    # Use the KMP search algorithm
    # to find it in O(N) time
    return 1 + KMPSearch(pat, text)
 
# Driver code
s1 = "geeks"
print(countRotations(s1))
 
# This code is contributed by divyamohan123

// C# implementation of the above approach
using System;
 
class GFG{
 
// Prints occurrences of txt[] in pat[]
static int KMPSearch(char []pat, char []txt)
{
    int M = pat.Length;
    int N = txt.Length;
  
    // Create lps[] that will hold the longest
    // prefix suffix values for pattern
    int []lps = new int[M];
  
    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);
  
    // Index for txt[] , // index for pat[]
    int i = 0;
    int j = 0;
     
    while (i < N)
    {
        if (pat[j] == txt[i])
        {
            j++;
            i++;
        }
  
        if (j == M)
        {
            return i - j ;
            //j = lps[j - 1];
        }
  
        // Mismatch after j matches
        else if (i < N && pat[j] != txt[i])
        {
             
            // Do not match lps[0..lps[j-1]]
            // characters, they will match anyway
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
    return 0;
}
  
// Fills lps[] for given pattern pat[0..M-1]
static void computeLPSArray(char []pat, int M,
                            int []lps)
{
     
    // Length of the previous longest
    // prefix suffix
    int len = 0;
     
    // lps[0] is always 0
    lps[0] = 0;
  
    // The loop calculates lps[i]
    // for i = 1 to M-1
    int i = 1;
     
    while (i < M)
    {
        if (pat[i] == pat[len])
        {
            len++;
            lps[i] = len;
            i++;
        }
 
        // (pat[i] != pat[len])
        else
        {
             
            // This is tricky. Consider the example.
            // AAACAAAA and i = 7. The idea is similar
            // to search step.
            if (len != 0) {
                len = lps[len - 1];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}
 
// Returns count of rotations to get the
// same string back
static int countRotations(string s)
{
     
    // Form a string excluding the first character
    // and concatenating the string at the end
    string s1 = s.Substring(1, s.Length - 1) + s;
  
    // Convert the string to character array
    char []pat = s.ToCharArray();
    char []text = s1.ToCharArray();
  
    // Use the KMP search algorithm
    // to find it in O(N) time
    return 1 + KMPSearch(pat, text);
}
  
// Driver code
public static void Main(params string []args)
{
    string s1 = "geeks";
     
    Console.Write(countRotations(s1));
}
}
 
// This code is contributed by pratham76

<script>
 
    // JavaScript implementation of the above approach
     
    // Prints occurrences of txt[] in pat[]
    function KMPSearch(pat, txt)
    {
        let M = pat.length;
        let N = txt.length;
 
        // Create lps[] that will hold the longest
        // prefix suffix values for pattern
        let lps = new Array(M);
        lps.fill(0);
 
        // Preprocess the pattern (calculate lps[] array)
        computeLPSArray(pat, M, lps);
 
        // Index for txt[] , // index for pat[]
        let i = 0;
        let j = 0;
 
        while (i < N)
        {
            if (pat[j] == txt[i])
            {
                j++;
                i++;
            }
 
            if (j == M)
            {
                return i - j ;
                //j = lps[j - 1];
            }
 
            // Mismatch after j matches
            else if (i < N && pat[j] != txt[i])
            {
 
                // Do not match lps[0..lps[j-1]]
                // characters, they will match anyway
                if (j != 0)
                    j = lps[j - 1];
                else
                    i = i + 1;
            }
        }
        return 0;
    }
 
    // Fills lps[] for given pattern pat[0..M-1]
    function computeLPSArray(pat, M, lps)
    {
 
        // Length of the previous longest
        // prefix suffix
        let len = 0;
 
        // lps[0] is always 0
        lps[0] = 0;
 
        // The loop calculates lps[i]
        // for i = 1 to M-1
        let i = 1;
 
        while (i < M)
        {
            if (pat[i] == pat[len])
            {
                len++;
                lps[i] = len;
                i++;
            }
 
            // (pat[i] != pat[len])
            else
            {
 
                // This is tricky. Consider the example.
                // AAACAAAA and i = 7. The idea is similar
                // to search step.
                if (len != 0) {
                    len = lps[len - 1];
                }
                else
                {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }
 
    // Returns count of rotations to get the
    // same string back
    function countRotations(s)
    {
 
        // Form a string excluding the first character
        // and concatenating the string at the end
        let s1 = s.substring(1, s.length) + s;
 
        // Convert the string to character array
        let pat = s.split('');
        let text = s1.split('');
 
        // Use the KMP search algorithm
        // to find it in O(N) time
        return 1 + KMPSearch(pat, text);
    }
     
    let s1 = "geeks";
      
    document.write(countRotations(s1));
 
</script>

5

Complejidad temporal: O(N).