String dada str . La tarea es encontrar la substring más larga que es un prefijo, un sufijo y una substring de la string dada, str . Si no existe tal string, imprima -1 .
Ejemplos:
Entrada: str = “fixprefixsuffix”
Salida: fix
“fix” es un prefijo, un sufijo y también está presente dentro de la string.
Entrada: str = “aaaa”
“aa” es un prefijo, sufijo y está presente dentro de la string.
Enfoque: calculemos el sufijo de prefijo más largo para todos los prefijos de string. el sufijo del prefijo más largo lps[i] es la longitud máxima del prefijo que también es el sufijo de la substring [0…i]. Puede ver más información sobre el sufijo de prefijo más largo en una descripción del algoritmo kmp .
La primera respuesta posible es un prefijo de longitud lps[n-1]. Si lps[n-1] = 0, no hay solución. Para verificar la primera respuesta posible, debe iterar sobre lps [i]. Si al menos uno de ellos es igual a lps[n-1] (pero no n-1th, por supuesto), encontraste la respuesta. La segunda respuesta posible es un prefijo de longitud lps[lps[n-1]-1]. Si lps[lps[n-1]-1] = 0, tampoco tiene solución. De lo contrario, puede estar seguro de que la respuesta ya se encuentra. Esta substring es un prefijo y un sufijo de nuestra string. Además, es un sufijo de un prefijo con longitud lps[n-1] que se coloca dentro de todas las strings. Esta solución funciona en O(n).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find longest prefix suffix
vector<int> compute_lps(string s)
{
int n = s.size();
// To store longest prefix suffix
vector<int> lps(n);
// Length of the previous
// longest prefix suffix
int len = 0;
// lps[0] is always 0
lps[0] = 0;
int i = 1;
// Loop calculates lps[i] for i = 1 to n - 1
while (i < n) {
if (s[i] == s[len]) {
len++;
lps[i] = len;
i++;
}
// (pat[i] != pat[len])
else {
if (len != 0)
len = lps[len - 1];
// Also, note that we do not increment
// i here
// If len = 0
else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
// Function to find the longest substring
// which is prefix as well as a
// sub-string of s[1...n-2]
void Longestsubstring(string s)
{
// Find longest prefix suffix
vector<int> lps = compute_lps(s);
int n = s.size();
// If lps of n-1 is zero
if (lps[n - 1] == 0) {
cout << -1;
return;
}
for (int i = 0; i < n - 1; i++) {
// At any position lps[i] equals to lps[n - 1]
if (lps[i] == lps[n - 1]) {
cout << s.substr(0, lps[i]);
return;
}
}
// If answer is not possible
if (lps[lps[n - 1] - 1] == 0)
cout << -1;
else
cout << s.substr(0, lps[lps[n - 1] - 1]);
}
// Driver code
int main()
{
string s = "fixprefixsuffix";
// function call
Longestsubstring(s);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to find longest prefix suffix
static int [] compute_lps(String s)
{
int n = s.length();
// To store longest prefix suffix
int [] lps = new int [n];
// Length of the previous
// longest prefix suffix
int len = 0;
// lps[0] is always 0
lps[0] = 0;
int i = 1;
// Loop calculates lps[i] for i = 1 to n - 1
while (i < n)
{
if (s.charAt(i) == s.charAt(len))
{
len++;
lps[i] = len;
i++;
}
// (pat[i] != pat[len])
else
{
if (len != 0)
len = lps[len - 1];
// Also, note that we do not increment
// i here
// If len = 0
else
{
lps[i] = 0;
i++;
}
}
}
return lps;
}
// Function to find the longest substring
// which is prefix as well as a
// sub-string of s[1...n-2]
static void Longestsubstring(String s)
{
// Find longest prefix suffix
int [] lps = compute_lps(s);
int n = s.length();
// If lps of n-1 is zero
if (lps[n - 1] == 0)
{
System.out.println(-1);
return;
}
for (int i = 0; i < n - 1; i++)
{
// At any position lps[i] equals to lps[n - 1]
if (lps[i] == lps[n - 1])
{
System.out.println(s.substring(0, lps[i]));
return;
}
}
// If answer is not possible
if (lps[lps[n - 1] - 1] == 0)
System.out.println(-1);
else
System.out.println(s.substring(0, lps[lps[n - 1] - 1]));
}
// Driver code
public static void main (String [] args)
{
String s = "fixprefixsuffix";
// function call
Longestsubstring(s);
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of the approach # Function to find longest prefix suffix def compute_lps(s): n = len(s) # To store longest prefix suffix lps = [0 for i in range(n)] # Length of the previous # longest prefix suffix Len = 0 # lps[0] is always 0 lps[0] = 0 i = 1 # Loop calculates lps[i] for i = 1 to n - 1 while (i < n): if (s[i] == s[Len]): Len += 1 lps[i] = Len i += 1 # (pat[i] != pat[Len]) else: if (Len != 0): Len = lps[Len - 1] # Also, note that we do not increment # i here # If Len = 0 else: lps[i] = 0 i += 1 return lps # Function to find the longest substring # which is prefix as well as a # sub-of s[1...n-2] def Longestsubstring(s): # Find longest prefix suffix lps = compute_lps(s) n = len(s) # If lps of n-1 is zero if (lps[n - 1] == 0): print(-1) exit() for i in range(0,n - 1): # At any position lps[i] equals to lps[n - 1] if (lps[i] == lps[n - 1]): print(s[0:lps[i]]) exit() # If answer is not possible if (lps[lps[n - 1] - 1] == 0): print(-1) else: print(s[0:lps[lps[n - 1] - 1]]) # Driver code s = "fixprefixsuffix" # function call Longestsubstring(s) # This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find longest prefix suffix
static int [] compute_lps(string s)
{
int n = s.Length;
// To store longest prefix suffix
int [] lps = new int [n];
// Length of the previous
// longest prefix suffix
int len = 0;
// lps[0] is always 0
lps[0] = 0;
int i = 1;
// Loop calculates lps[i] for i = 1 to n - 1
while (i < n)
{
if (s[i] == s[len])
{
len++;
lps[i] = len;
i++;
}
// (pat[i] != pat[len])
else
{
if (len != 0)
len = lps[len - 1];
// Also, note that we do not increment
// i here
// If len = 0
else
{
lps[i] = 0;
i++;
}
}
}
return lps;
}
// Function to find the longest substring
// which is prefix as well as a
// sub-string of s[1...n-2]
static void Longestsubstring(string s)
{
// Find longest prefix suffix
int [] lps = compute_lps(s);
int n = s.Length;
// If lps of n-1 is zero
if (lps[n - 1] == 0)
{
Console.WriteLine(-1);
return;
}
for (int i = 0; i < n - 1; i++)
{
// At any position lps[i] equals to lps[n - 1]
if (lps[i] == lps[n - 1])
{
Console.WriteLine(s.Substring(0, lps[i]));
return;
}
}
// If answer is not possible
if (lps[lps[n - 1] - 1] == 0)
Console.WriteLine(-1);
else
Console.WriteLine(s.Substring(0, lps[lps[n - 1] - 1]));
}
// Driver code
public static void Main ()
{
string s = "fixprefixsuffix";
// function call
Longestsubstring(s);
}
}
// This code is contributed by ihritik
PHP
<?php
// Python3 implementation of the approach
// Function to find longest prefix suffix
function compute_lps($s)
{
$n = strlen($s);
// To store longest prefix suffix
$lps = array();
// Length of the previous
// longest prefix suffix
$len = 0;
// lps[0] is always 0
$lps[0] = 0;
$i = 1;
// Loop calculates lps[i] for i = 1 to n - 1
while ($i < $n)
{
if ($s[$i] == $s[$len])
{
$len++;
$lps[$i] = $len;
$i++;
}
// (pat[i] != pat[len])
else
{
if ($len != 0)
$len = $lps[$len - 1];
// Also, note that we do not increment
// i here
// If len = 0
else
{
$lps[$i] = 0;
$i++;
}
}
}
return $lps;
}
// Function to find the longest substring
// which is prefix as well as a
// sub-string of s[1...n-2]
function Longestsubstring($s)
{
// Find longest prefix suffix
$lps = compute_lps($s);
$n = strlen($s);
// If lps of n-1 is zero
if ($lps[$n - 1] == 0)
{
echo -1;
return;
}
for ($i = 0; $i < $n - 1; $i++)
{
// At any position lps[i] equals to lps[n - 1]
if ($lps[$i] == $lps[$n - 1])
{
echo substr($s, 0, $lps[$i]);
return;
}
}
// If answer is not possible
if ($lps[$lps[$n - 1] - 1] == 0)
echo -1;
else
echo substr($s, 0, $lps[$lps[$n - 1] - 1]);
}
// Driver code
$s = "fixprefixsuffix";
// function call
Longestsubstring($s);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to find longest prefix suffix
function compute_lps(s)
{
var n = s.length;
// To store longest prefix suffix
var lps = Array(n);
// Length of the previous
// longest prefix suffix
var len = 0;
// lps[0] is always 0
lps[0] = 0;
var i = 1;
// Loop calculates lps[i] for i = 1 to n - 1
while (i < n) {
if (s[i] == s[len]) {
len++;
lps[i] = len;
i++;
}
// (pat[i] != pat[len])
else {
if (len != 0)
len = lps[len - 1];
// Also, note that we do not increment
// i here
// If len = 0
else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
// Function to find the longest substring
// which is prefix as well as a
// sub-string of s[1...n-2]
function Longestsubstring( s)
{
// Find longest prefix suffix
var lps = compute_lps(s);
var n = s.length;
// If lps of n-1 is zero
if (lps[n - 1] == 0) {
document.write( -1);
return;
}
for (var i = 0; i < n - 1; i++) {
// At any position lps[i] equals to lps[n - 1]
if (lps[i] == lps[n - 1]) {
document.write( s.substring(0, lps[i]));
return;
}
}
// If answer is not possible
if (lps[lps[n - 1] - 1] == 0)
document.write( -1);
else
document.write( s.substr(0, lps[lps[n - 1] - 1]));
}
// Driver code
var s = "fixprefixsuffix";
// function call
Longestsubstring(s);
</script>
Producción:
fix
Complejidad Temporal: O(N)
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA