Imprime el prefijo más largo de la string dada que también es el sufijo de la misma string

Dada la string str , la tarea es encontrar el prefijo más largo que también es el sufijo de la string dada. El prefijo y el sufijo no deben superponerse. Si no existe tal prefijo, imprima -1 .

Ejemplos: 

Entrada: str = “aabcdaabc” 
Salida: aabc 
La string “aabc” es el 
prefijo más largo que también es un sufijo.

Entrada: str = “aaaa” 
Salida: aa  

Enfoque: La idea es utilizar el algoritmo de preprocesamiento de la búsqueda KMP . En este algoritmo, creamos una array lps que almacena los siguientes valores:  

lps[i] = el prefijo propio más largo de pat[0..i] 
que también es un sufijo de pat[0..i] .  

Obtenemos la longitud usando el enfoque anterior, luego imprimimos la misma cantidad de caracteres desde el frente, que es nuestra respuesta. 

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Returns length of the longest prefix
// which is also suffix and the two do
// not overlap. This function mainly is
// copy of computeLPSArray() in KMP Algorithm
int LengthlongestPrefixSuffix(string s)
{
    int n = s.length();
 
    int lps[n];
 
    // lps[0] is always 0
    lps[0] = 0;
 
    // Length of the previous
    // longest prefix suffix
    int len = 0;
 
    // Loop to calculate lps[i]
    // for i = 1 to n - 1
    int i = 1;
    while (i < n) {
        if (s[i] == s[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        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];
 
                // Also, note that we do
                // not increment i here
            }
 
            // If len = 0
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
 
    int res = lps[n - 1];
 
    // Since we are looking for
    // non overlapping parts
    return (res > n / 2) ? n / 2 : res;
}
 
// Function that returns the prefix
string longestPrefixSuffix(string s)
{
    // Get the length of the longest prefix
    int len = LengthlongestPrefixSuffix(s);
 
    // Stores the prefix
    string prefix = "";
 
    // Traverse and add characters
    for (int i = 0; i < len; i++)
        prefix += s[i];
 
    // Returns the prefix
    return prefix;
}
 
// Driver code
int main()
{
    string s = "abcab";
    string ans = longestPrefixSuffix(s);
    if (ans == "")
        cout << "-1";
    else
        cout << ans;
 
    return 0;
}

Java

// Java implementation of the approach
class GfG
{
 
// Returns length of the longest prefix
// which is also suffix and the two do
// not overlap. This function mainly is
// copy of computeLPSArray() in KMP Algorithm
static int LengthlongestPrefixSuffix(String s)
{
    int n = s.length();
 
    int lps[] = new int[n];
 
    // lps[0] is always 0
    lps[0] = 0;
 
    // Length of the previous
    // longest prefix suffix
    int len = 0;
 
    // Loop to calculate lps[i]
    // for i = 1 to n - 1
    int i = 1;
    while (i < n)
    {
        if (s.charAt(i) == s.charAt(len))
        {
            len++;
            lps[i] = len;
            i++;
        }
        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];
 
                // Also, note that we do
                // not increment i here
            }
 
            // If len = 0
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
 
    int res = lps[n - 1];
 
    // Since we are looking for
    // non overlapping parts
    return (res > n / 2) ? n / 2 : res;
}
 
// Function that returns the prefix
static String longestPrefixSuffix(String s)
{
    // Get the length of the longest prefix
    int len = LengthlongestPrefixSuffix(s);
 
    // Stores the prefix
    String prefix = "";
 
    // Traverse and add characters
    for (int i = 0; i < len; i++)
        prefix += s.charAt(i);
 
    // Returns the prefix
    return prefix;
}
 
// Driver code
public static void main(String[] args)
{
    String s = "abcab";
    String ans = longestPrefixSuffix(s);
    if (ans == "")
        System.out.println("-1");
    else
        System.out.println(ans);
}
}

Python3

# Python 3 implementation of the approach
 
# Returns length of the longest prefix
# which is also suffix and the two do
# not overlap. This function mainly is
# copy of computeLPSArray() in KMP Algorithm
def LengthlongestPrefixSuffix(s):
    n = len(s)
 
    lps = [0 for i in range(n)]
 
    # Length of the previous
    # longest prefix suffix
    len1 = 0
 
    # Loop to calculate lps[i]
    # for i = 1 to n - 1
    i = 1
    while (i < n):
        if (s[i] == s[len1]):
            len1 += 1
            lps[i] = len1
            i += 1
         
        else:
             
            # This is tricky. Consider
            # the example. AAACAAAA
            # and i = 7. The idea is
            # similar to search step.
            if (len1 != 0):
                len1 = lps[len1 - 1]
 
                # Also, note that we do
                # not increment i here
             
            # If len = 0
            else:
                lps[i] = 0
                i += 1
 
    res = lps[n - 1]
     
    # Since we are looking for
    # non overlapping parts
    if (res > int(n / 2)):
        return int(n / 2)
    else:
        return res
 
# Function that returns the prefix
def longestPrefixSuffix(s):
     
    # Get the length of the longest prefix
    len1 = LengthlongestPrefixSuffix(s)
 
    # Stores the prefix
    prefix = ""
 
    # Traverse and add characters
    for i in range(len1):
        prefix += s[i]
 
    # Returns the prefix
    return prefix
 
# Driver code
if __name__ == '__main__':
    s = "abcab"
    ans = longestPrefixSuffix(s)
    if (ans == ""):
        print("-1")
    else:
        print(ans)
         
# This code is contributed by
# Surendra_Gangwar

C#

// C# implementation of the approach
using System;
 
class GfG
{
 
    // Returns length of the longest prefix
    // which is also suffix and the two do
    // not overlap. This function mainly is
    // copy of computeLPSArray() in KMP Algorithm
    static int LengthlongestPrefixSuffix(string s)
    {
        int n = s.Length;
     
        int []lps = new int[n];
     
        // lps[0] is always 0
        lps[0] = 0;
     
        // Length of the previous
        // longest prefix suffix
        int len = 0;
     
        // Loop to calculate lps[i]
        // for i = 1 to n - 1
        int i = 1;
        while (i < n)
        {
            if (s[i] == s[len])
            {
                len++;
                lps[i] = len;
                i++;
            }
            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];
     
                    // Also, note that we do
                    // not increment i here
                }
     
                // If len = 0
                else
                {
                    lps[i] = 0;
                    i++;
                }
            }
        }
     
        int res = lps[n - 1];
     
        // Since we are looking for
        // non overlapping parts
        return (res > n / 2) ? n / 2 : res;
    }
     
    // Function that returns the prefix
    static String longestPrefixSuffix(string s)
    {
        // Get the length of the longest prefix
        int len = LengthlongestPrefixSuffix(s);
     
        // Stores the prefix
        string prefix = "";
     
        // Traverse and add characters
        for (int i = 0; i < len; i++)
            prefix += s[i];
     
        // Returns the prefix
        return prefix;
    }
     
    // Driver code
    public static void Main()
    {
        string s = "abcab";
        string ans = longestPrefixSuffix(s);
        if (ans == "")
            Console.WriteLine("-1");
        else
            Console.WriteLine(ans);
    }
}
 
// This code is contributed by Ryuga

Javascript

<script>
 
// JavaScript implementation of the approach
 
 
// Returns length of the longest prefix
// which is also suffix and the two do
// not overlap. This function mainly is
// copy of computeLPSArray() in KMP Algorithm
function LengthlongestPrefixSuffix(s)
{
    var n = s.length;
 
    var lps = Array.from({length: n}, (_, i) => 0);
 
    // lps[0] is always 0
    lps[0] = 0;
 
    // Length of the previous
    // longest prefix suffix
    var len = 0;
 
    // Loop to calculate lps[i]
    // for i = 1 to n - 1
    var i = 1;
    while (i < n)
    {
        if (s.charAt(i) == s.charAt(len))
        {
            len++;
            lps[i] = len;
            i++;
        }
        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];
 
                // Also, note that we do
                // not increment i here
            }
 
            // If len = 0
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
 
    var res = lps[n - 1];
 
    // Since we are looking for
    // non overlapping parts
    return (res > n / 2) ? n / 2 : res;
}
 
// Function that returns the prefix
function longestPrefixSuffix(s)
{
    // Get the length of the longest prefix
    var len = LengthlongestPrefixSuffix(s);
 
    // Stores the prefix
    var prefix = "";
 
    // Traverse and add characters
    for (var i = 0; i < len; i++)
        prefix += s.charAt(i);
 
    // Returns the prefix
    return prefix;
}
 
// Driver code
var s = "abcab";
var ans = longestPrefixSuffix(s);
if (ans == "")
    document.write("-1");
else
    document.write(ans);
 
// This code contributed by shikhasingrajput
 
</script>
Producción: 

ab

 

Complejidad de tiempo: O (N), ya que estamos usando un ciclo para atravesar N veces para construir la array. Donde N es la longitud de la string.

Espacio auxiliar: O (N), ya que estamos usando espacio adicional para la array lps. Donde N es la longitud de la string.

Publicación traducida automáticamente

Artículo escrito por Striver 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 *