Eliminar el prefijo más largo de la string que tiene una substring duplicada

Dada una string S de longitud N , la tarea es eliminar el prefijo más largo de la string que tiene al menos una substring duplicada presente en S.

Nota: la substring duplicada no puede ser el prefijo en sí

Ejemplos: 

Entrada: S = «GeeksforGeeks»
Salida: «forGeeks»
Explicación: La substring más larga que tiene un duplicado es «Geeks».
Después de eliminar esto, la string restante se convierte en «forGeeks».

Entrada: S = “aaaa”
Salida: “a”
Explicación: Aquí el prefijo más largo que tiene una substring duplicada es “aaaa”.
Entonces, después de eliminar esto, la string restante es «a». 
Tenga en cuenta que la string completa no está seleccionada porque entonces la string duplicada es el prefijo en sí.

Planteamiento: El problema se puede resolver a partir de la siguiente idea:

Encuentre todos los caracteres que pueden ser un punto de partida de una substring que es un duplicado del prefijo. Luego, desde estos puntos, encuentre el duplicado del prefijo más largo y elimine ese prefijo.

Siga la ilustración a continuación para una mejor comprensión.

Ilustración:

Por ejemplo, tome S = «aaaa»

Los posibles puntos de partida pueden estar en los índices 1, 2, 3, 4.

Para índice 1: El posible duplicado del prefijo es “aaaa”.
Tiene longitud = 4

Para índice 2: El posible duplicado del prefijo es “aaa”.
Tiene longitud = 3

Para índice 3: El posible duplicado del prefijo es “aa”.
Tiene longitud = 2

Para índice 4: El posible duplicado del prefijo es “a”.
Tiene longitud = 1

Así que elimine el prefijo de longitud 4. Por lo tanto, la string se convierte en «a»

Siga el enfoque mencionado a continuación para resolver el problema:

• Use dos punteros: uno al comienzo del prefijo (digamos i , que inicialmente es 0 ) y el otro (digamos j ) para encontrar el punto de inicio de todas las substrings duplicadas posibles.
• Iterar j de 1 a N:
  • Si S[j] coincide con S[i], use un puntero (digamos k) e itere tanto i como k para encontrar la longitud de la substring a partir de j , que es un duplicado del prefijo.
  • Actualice la longitud máxima.
  • Establezca i nuevamente en 0.
• Eliminar el prefijo de longitud máxima.

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

// C++ code for the above approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to delete the longest prefix
string delPrefix(string S)
{
    if (S.size() == 1)
        return S;
    int i = 0, maxi = 0;
 
    // Loop to find the
    // longest duplicate of prefix
    for (int j = 1; j < S.size(); j++) {
        int k = j;
        while (k < S.size() and S[k] == S[i]) {
            k++;
            i++;
        }
        maxi = max(maxi, i);
        i = 0;
    }
    return S.substr(maxi);
}
 
// Driver code
int main()
{
    string S = "aaaaa";
    string ans = delPrefix(S);
 
    // Function call
    cout << ans;
    return 0;
}

// Java code for the above approach
import java.io.*;
 
class GFG
{
   
  // Function to delete the longest prefix
  public static String delPrefix(String S)
  {
    if (S.length() == 1)
      return S;
    int i = 0, maxi = 0;
 
    // Loop to find the
    // longest duplicate of prefix
    for (int j = 1; j < S.length(); j++) {
      int k = j;
      while (k < S.length()
             && S.charAt(k) == S.charAt(i)) {
        k++;
        i++;
      }
      maxi = Math.max(maxi, i);
      i = 0;
    }
    return S.substring(maxi);
  }
  public static void main(String[] args)
  {
    String S = "aaaaa";
    String ans = delPrefix(S);
 
    // Function call
    System.out.print(ans);
  }
}
 
// This code is contributed by Rohit Pradhan

# Python code for the above approach:
 
# Function to delete the longest prefix
def delPrefix(S):
 
    if (len(S) == 1):
        return S
    i = 0
    maxi = 0
 
    # Loop to find the
    # longest duplicate of prefix
    for j in (1, len(S)+1):
        k = j
        while (k < len(S) and S[k] == S[i]):
            k = k + 1
            i = i + 1
 
        maxi = max(maxi, i)
        i = 0
 
    return S[maxi:]
 
# Driver code
S = "aaaaa"
ans = delPrefix(S)
 
# Function call
print(ans)
 
# This code is contributed by Taranpreet

// C# code for the above approach
using System;
 
public class GFG{
 
  // Function to delete the longest prefix
  public static string delPrefix(string S)
  {
    if (S.Length == 1)
      return S;
    int i = 0, maxi = 0;
 
    // Loop to find the
    // longest duplicate of prefix
    for (int j = 1; j < S.Length; j++) {
      int k = j;
      while (k < S.Length
             && S[k] == S[i]) {
        k++;
        i++;
      }
      maxi = Math.Max(maxi, i);
      i = 0;
    }
    return S.Substring(maxi);
  }
 
  static public void Main (){
 
    string S = "aaaaa";
    string ans = delPrefix(S);
 
    // Function call
    Console.Write(ans);
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
       // JavaScript code for the above approach
       function delPrefix(S) {
           if (S.length == 1)
               return S;
           let i = 0, maxi = 0;
 
           // Loop to find the
           // longest duplicate of prefix
           for (let j = 1; j < S.length; j++) {
               let k = j;
               while (k < S.length && S[k] == S[i]) {
                   k++;
                   i++;
               }
               maxi = Math.max(maxi, i);
               i = 0;
           }
           return S.slice(maxi);
       }
 
       // Driver code
       let S = "aaaaa";
       let ans = delPrefix(S);
 
       // Function call
       document.write(ans)
        
   // This code is contributed by Potta Lokesh
   </script>

a

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)