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.