Codifique la string dada reemplazando las substrings con el mismo prefijo con *

String dada str de tamaño N que contiene solo letras minúsculas en inglés . La tarea es encriptar la string de modo que las substrings que tengan el mismo prefijo sean reemplazadas por un * . Genere la string cifrada.

Nota: si la string se puede cifrar de varias formas, busque la string cifrada más pequeña. 

Ejemplos:

Entrada: str = “ababcababcd”
Salida: ab*c*d
Explicación: La substring “ababc” a partir del 5.° índice (indexación basada en 0) se puede reemplazar por un ‘ *’ . Entonces la string se convierte en «ababcababcd» -> «ababc*d». Ahora, la substring «ab» que comienza en el segundo índice se puede reemplazar nuevamente con un ‘*’. Entonces la string se convierte en «ab*c*d»

Entrada: str = “zzzzzzz”
Salida: z*z*z
Explicación: La string se puede cifrar de 2 formas: “z*z*z” y “z**zzz”. De los dos, «z*z*z» es más pequeño en longitud.

Enfoque: una solución simple para generar la string cifrada más pequeña es encontrar la substring repetida más larga que no se superponga y cifrar esa substring primero. Para implementar esto utilice los siguientes pasos:

• Cree una pila para almacenar la string cifrada.
• Declare dos punteros (i y j) para señalar el primer índice y el índice medio respectivamente.
• Ahora comience a atravesar la string y repita el bucle hasta que se escanee toda la string. Siga los pasos mencionados a continuación para cada iteración:
  • Compare la substring del índice i y j .
  • Si ambas substrings son iguales , repita el mismo proceso en esta substring y almacene la string restante en la pila.
  • De lo contrario, disminuya el valor del segundo puntero ( j ) en 1.
• Ahora extraiga todos los elementos de la pila y agregue un símbolo «*» y luego guárdelo en una string de salida.
• Devuelve la string cifrada.

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

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to generate the encrypted string
string compress(string str)
{
    // Stack to store encrypted string
    stack<string> st;
  
    // Variable to store length of string
    int N = str.length();
  
    // Variable to point 1st and middle index
    int i = 0, j = N / 2;
  
    // Repeat the loop until
    // the entire string is checked
    while (j > 0) {
        int mid = j;
  
        // Compare the substring
        // from index 0 to mid-1
        // with the rest of the substring
        // after mid.
        for (i = 0; i < mid && str[i] == str[j]; i++, j++)
            ;
  
        // If both substrings are equal
        // then repeat the same process
        // on this substring and store
        // the remaining string into stack
        if (i == mid) {
            st.push(str.substr(j, N - 1));
  
            // Update the value of
            // string 'str' with the
            // longest repeating substring
            str = str.substr(0, i);
  
            // Set the new string length to n
            N = mid;
  
            // Initialize the 2nd pointer
            // from the mid of new string
            j = N / 2;
        }
  
        // If both substrings are not equal
        // then decrement the 2nd pointer by 1
        else {
            j = mid - 1;
        }
    }
  
    // Pop all the elements from the stack
    // append a symbol '*' and store
    // in a output string
    while (!st.empty()) {
        str = str + "*" + st.top();
        st.pop();
    }
  
    return str;
}
  
// Driver code
int main()
{
    // Declare and initialize the string
    string str = "zzzzzzz";
  
    cout << compress(str) << "\n";
    return 0;
}

// Java code to implement the above approach
  
import java.util.*;
  
class GFG{
  
// Function to generate the encrypted String
static String compress(String str)
{
    // Stack to store encrypted String
    Stack<String> st = new Stack<String>();
  
    // Variable to store length of String
    int N = str.length();
  
    // Variable to point 1st and middle index
    int i = 0, j = N / 2;
  
    // Repeat the loop until
    // the entire String is checked
    while (j > 0) {
        int mid = j;
  
        // Compare the subString
        // from index 0 to mid-1
        // with the rest of the subString
        // after mid.
        for (i = 0; i < mid && str.charAt(i) == str.charAt(j); i++, j++)
            ;
  
        // If both subStrings are equal
        // then repeat the same process
        // on this subString and store
        // the remaining String into stack
        if (i == mid) {
            st.add(str.substring(j,  N));
  
            // Update the value of
            // String 'str' with the
            // longest repeating subString
            str = str.substring(0, i);
  
            // Set the new String length to n
            N = mid;
  
            // Initialize the 2nd pointer
            // from the mid of new String
            j = N / 2;
        }
  
        // If both subStrings are not equal
        // then decrement the 2nd pointer by 1
        else {
            j = mid - 1;
        }
    }
  
    // Pop all the elements from the stack
    // append a symbol '*' and store
    // in a output String
    while (!st.isEmpty()) {
        str = str + "*" + st.peek();
        st.pop();
    }
  
    return str;
}
  
// Driver code
public static void main(String[] args)
{
    // Declare and initialize the String
    String str = "zzzzzzz";
  
    System.out.print(compress(str)+ "\n");
}
}
  
// This code is contributed by 29AjayKumar

# Python code for the above approach
  
# Function to generate the encrypted string
def compress(str):
  
    # Stack to store encrypted string
    st = []
  
    # Variable to store length of string
    N = len(str)
  
    # Variable to point 1st and middle index
    i = 0
    j = (int)(N / 2)
  
    # Repeat the loop until
    # the entire string is checked
    while (j > 0):
        mid = j
  
        # Compare the substring
        # from index 0 to mid-1
        # with the rest of the substring
        # after mid.
        i=0
        while(str[i] == str[j] and i < mid):
            i += 1
            j += 1
        # If both substrings are equal
        # then repeat the same process
        # on this substring and store
        # the remaining string into stack
        if (i == mid):
            st.append(str[j:N])
  
            # Update the value of
            # string 'str' with the
            # longest repeating substring
            str = str[0:i]
  
            # Set the new string length to n
            N = mid
  
            # Initialize the 2nd pointer
            # from the mid of new string
            j = N // 2
  
        # If both substrings are not equal
        # then decrement the 2nd pointer by 1
        else:
            j = mid - 1
  
    # Pop all the elements from the stack
    # append a symbol '*' and store
    # in a output string
    while (len(st) != 0):
        str = str + '*' + st[len(st) - 1]
        st.pop()
    return str
  
# Driver code
  
# Declare and initialize the string
str = "zzzzzzz"
print(compress(str))
  
# This code is contributed by Saurabh jaiswal

// C# code to implement the above approach
using System;
using System.Collections.Generic;
  
public class GFG{
  
// Function to generate the encrypted String
static String compress(String str)
{
    // Stack to store encrypted String
    Stack<String> st = new Stack<String>();
  
    // Variable to store length of String
    int N = str.Length;
  
    // Variable to point 1st and middle index
    int i = 0, j = N / 2;
  
    // Repeat the loop until
    // the entire String is checked
    while (j > 0) {
        int mid = j;
  
        // Compare the subString
        // from index 0 to mid-1
        // with the rest of the subString
        // after mid.
        for (i = 0; i < mid && str[i] == str[j]; i++, j++)
            ;
  
        // If both subStrings are equal
        // then repeat the same process
        // on this subString and store
        // the remaining String into stack
        if (i == mid) {
            st.Push(str.Substring(j,  N-j));
  
            // Update the value of
            // String 'str' with the
            // longest repeating subString
            str = str.Substring(0, i);
  
            // Set the new String length to n
            N = mid;
  
            // Initialize the 2nd pointer
            // from the mid of new String
            j = N / 2;
        }
  
        // If both subStrings are not equal
        // then decrement the 2nd pointer by 1
        else {
            j = mid - 1;
        }
    }
  
    // Pop all the elements from the stack
    // append a symbol '*' and store
    // in a output String
    while (st.Count!=0) {
        str = str + "*" + st.Peek();
        st.Pop();
    }
  
    return str;
}
  
// Driver code
public static void Main(String[] args)
{
    // Declare and initialize the String
    String str = "zzzzzzz";
  
    Console.Write(compress(str)+ "\n");
}
}
  
// This code is contributed by shikhasingrajput

<script>
  // JavaScript code for the above approach
 
  // Function to generate the encrypted string
  function compress(str) 
  {
    
    // Stack to store encrypted string
    let st = [];
 
    // Variable to store length of string
    let N = str.length;
 
    // Variable to point 1st and middle index
    let i = 0, j = Math.floor(N / 2);
 
    // Repeat the loop until
    // the entire string is checked
    while (j > 0) {
      let mid = j;
 
      // Compare the substring
      // from index 0 to mid-1
      // with the rest of the substring
      // after mid.
      for (i = 0; i < mid && str[i] == str[j]; i++, j++)
        ;
 
      // If both substrings are equal
      // then repeat the same process
      // on this substring and store
      // the remaining string into stack
      if (i == mid) {
        st.push(str.slice(j, N));
 
        // Update the value of
        // string 'str' with the
        // longest repeating substring
        str = str.slice(0, i);
 
        // Set the new string length to n
        N = mid;
 
        // Initialize the 2nd pointer
        // from the mid of new string
        j = Math.floor(N / 2);
      }
 
      // If both substrings are not equal
      // then decrement the 2nd pointer by 1
      else {
        j = mid - 1;
      }
    }
 
    // Pop all the elements from the stack
    // append a symbol '*' and store
    // in a output string
    while (st.length != 0) {
      str = str + '*' + st[st.length - 1];
      st.pop();
    }
 
    return str;
  }
 
  // Driver code
 
  // Declare and initialize the string
  let str = "zzzzzzz";
 
  document.write(compress(str) + '<br>');
 
// This code is contributed by Potta Lokesh
</script>

z*z*z

Complejidad de Tiempo: O(N. Log(N))
Espacio Auxiliar: O(N)