Dada una string s, encuentre la longitud del prefijo más largo, que también es un sufijo. El prefijo y el sufijo no deben superponerse.
Ejemplos:
Input : aabcdaabc Output : 4 The string "aabc" is the longest prefix which is also suffix. Input : abcab Output : 2 Input : aaaa Output : 2
Solución simple: dado que no se permite la superposición de prefijos y sufijos, partimos la string desde el medio y comenzamos a hacer coincidir las strings izquierda y derecha. Si tienen el mismo tamaño de retorno de una string, de lo contrario, intentan longitudes más cortas en ambos lados.
¡A continuación se muestra una solución al enfoque anterior!
C++
// CPP program to find length of the
// longest prefix which is also suffix
#include <bits/stdc++.h>
using namespace std;
// Function to find largest prefix
// which is also a suffix
int largest_prefix_suffix(const std::string
&str)
{
int n = str.length();
// if n is less than 2
if(n < 2) {
return 0;
}
int len = 0;
int i = 1;
// Iterate i till n
while(i < n)
{
// If str[i] is equal to
// str[len]
if(str[i] == str[len])
{
++len;
++i;
}
else
{
i = i - len + 1;
len = 0;
}
}
// Return len
return len>n/2? len/2:len;
}
// Driver code
int main()
{
string s = "blablabla";
// Function Call
cout << largest_prefix_suffix(s);
return 0;
}
Java
// Java program to find length of the longest
// prefix which is also suffix
class GFG
{
// Function to find largest prefix
// which is also a suffix
static int longestPrefixSuffix(String s)
{
int n = s.length();
// If n is less than 2
if(n < 2) {
return 0;
}
int len = 0;
int i = (n + 1)/2;
// Iterate i till n
while(i < n)
{
// If s.charAt(i) is equal to
// s.charAt(len)
if(s.charAt(i) == s.charAt(len))
{
++len;
++i;
}
else
{
i = i - len + 1;
len = 0;
}
}
// Return len
return len;
}
// Driver code
public static void main (String[] args)
{
String s = "abcaabc";
System.out.println(longestPrefixSuffix(s));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find length # of the longest prefix which # is also suffix def longestPrefixSuffix(s) : n = len(s) for res in range(n // 2, 0, -1) : # Check for shorter lengths # of first half. prefix = s[0: res] suffix = s[n - res: n] if (prefix == suffix) : return res # if no prefix and suffix match # occurs return 0 # Driver Code if __name__ == "__main__": s = "blablabla" print(longestPrefixSuffix(s)) # This code is contributed by Nikita Tiwari.
C#
// C# program to find length of the longest
// prefix which is also suffix
using System;
class GFG
{
// Function to find largest prefix
// which is also a suffix
static int longestPrefixSuffix(String s)
{
int n = s.Length;
// if n is less than 2
if(n < 2) {
return 0;
}
int len = 0;
int i = (n + 1)/2;
// Iterate i till n
while(i < n)
{
// If str[i] is equal to
// str[len]
if(str[i] == str[len])
{
++len;
++i;
}
else
{
i = i - len + 1;
len = 0;
}
}
// Return len
return len;
}
// Driver code
public static void Main ()
{
String s = "blablabla";
Console.WriteLine(longestPrefixSuffix(s));
}
}
// This code is contributed by vt_m.
Javascript
<script>
// JavaScript program to find length of the longest
// prefix which is also suffix
// Function to find largest prefix
// which is also a suffix
function longestPrefixSuffix(s)
{
var n = s.length;
// If n is less than 2
if(n < 2) {
return 0;
}
var len = 0;
var i = (n + 1)/2;
// Iterate i till n
while(i < n)
{
// If s[i] is equal to
// s[len]
if(s[i] == s[len])
{
++len;
++i;
}
else
{
i = i - len + 1;
len = 0;
}
}
// Return len
return len;
}
// Driver code
var s = "blablabla";
document.write(longestPrefixSuffix(s));
// This code contributed by shikhasingrajput
</script>
Producción:
3
Solución Eficiente: La idea es utilizar el algoritmo de búsqueda KMP de preprocesamiento . En el algoritmo de preprocesamiento, 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].
C++
// Efficient CPP program to find length of
// the longest prefix which is also suffix
#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 computeLPSArray() of in below post
// https://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
int longestPrefixSuffix(string s)
{
int n = s.length();
int lps[n];
lps[0] = 0; // lps[0] is always 0
// length of the previous
// longest prefix suffix
int len = 0;
// the loop calculates 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 // (pat[i] != pat[len])
{
// 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
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
int res = lps[n-1];
// Since we are looking for
// non overlapping parts.
return (res > n/2)? res/2 : res;
}
// Driver program to test above function
int main()
{
string s = "abcab";
cout << longestPrefixSuffix(s);
return 0;
}
Java
// Efficient Java program to find length of
// the longest prefix which is also suffix
class GFG
{
// Returns length of the longest prefix
// which is also suffix and the two do
// not overlap. This function mainly is
// copy computeLPSArray() of in below post
// https://www.geeksforgeeks.org/searching-
// for-patterns-set-2-kmp-algorithm/
static int longestPrefixSuffix(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;
// the loop calculates 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++;
}
// (pat[i] != pat[len])
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;
}
// Driver program
public static void main (String[] args)
{
String s = "abcab";
System.out.println(longestPrefixSuffix(s));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Efficient Python 3 program # to find length of # the longest prefix # which is also suffix # Returns length of the longest prefix # which is also suffix and the two do # not overlap. This function mainly is # copy computeLPSArray() of in below post # https://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/ def longestPrefixSuffix(s) : n = len(s) lps = [0] * n # lps[0] is always 0 # length of the previous # longest prefix suffix l = 0 # the loop calculates lps[i] # for i = 1 to n-1 i = 1 while (i < n) : if (s[i] == s[l]) : l = l + 1 lps[i] = l i = i + 1 else : # (pat[i] != pat[len]) # This is tricky. Consider # the example. AAACAAAA # and i = 7. The idea is # similar to search step. if (l != 0) : l = lps[l-1] # Also, note that we do # not increment i here else : # if (len == 0) lps[i] = 0 i = i + 1 res = lps[n-1] # Since we are looking for # non overlapping parts. if(res > n/2) : return n//2 else : return res # Driver program to test above function s = "abcab" print(longestPrefixSuffix(s)) # This code is contributed # by Nikita Tiwari.
C#
// Efficient C# program to find length of
// the longest prefix which is also suffix
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 computeLPSArray() of in below post
// https://www.geeksforgeeks.org/searching-
// for-patterns-set-2-kmp-algorithm/
static int longestPrefixSuffix(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;
// the loop calculates lps[i]
// for i = 1 to n-1
int i = 1;
while (i < n)
{
if (s[i] == s[len])
{
len++;
lps[i] = len;
i++;
}
// (pat[i] != pat[len])
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;
}
// Driver program
public static void Main ()
{
string s = "abcab";
Console.WriteLine(longestPrefixSuffix(s));
}
}
// This code is contributed by vt_m.
PHP
<?php
// Efficient PHP program to find length of
// the longest prefix which is also suffix
// Returns length of the longest prefix
// which is also suffix and the two do
// not overlap. This function mainly is
// copy computeLPSArray() of in below post
// https://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
function longestPrefixSuffix($s)
{
$n = strlen($s);
$lps[$n] = NULL;
// lps[0] is always 0
$lps[0] = 0;
// length of the previous
// longest prefix suffix
$len = 0;
// the loop calculates lps[i]
// for i = 1 to n-1
$i = 1;
while ($i < $n)
{
if ($s[$i] == $s[$len])
{
$len++;
$lps[$i] = $len;
$i++;
}
// (pat[i] != pat[len])
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++;
}
}
}
$res = $lps[$n-1];
// Since we are looking for
// non overlapping parts.
return ($res > $n/2)? $n/2 : $res;
}
// Driver Code
$s = "abcab";
echo longestPrefixSuffix($s);
// This code is contributed by nitin mittal
?>
Javascript
<script>
// Efficient javascript program to find length of
// the longest prefix which is also suffix{
// Returns length of the longest prefix
// which is also suffix and the two do
// not overlap. This function mainly is
// copy computeLPSArray() of in below post
// https://www.geeksforgeeks.org/searching-
// for-patterns-set-2-kmp-algorithm/
function longestPrefixSuffix(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;
// the loop calculates 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++;
}
// (pat[i] != pat[len])
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;
}
// Driver program
var s = "abcab";
document.write(longestPrefixSuffix(s));
// This code is contributed by 29AjayKumar
</script>
Producción:
2
Consulte la explicación de la función de búsqueda de computeLPSArray() de KMP .
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(n)
Solución usando RegEx:
Python3
# Python code to find length of the longest # prefix which is also suffix import re s = "ABCABCABCABCABC" # Example input print(len(re.findall(r'^(\w*).*\1$',s)[0]))
Producción:
6
Solución eficiente: la idea es atravesar el sufijo en orden inverso e intentar encontrar una coincidencia en la primera mitad de la string (posible prefijo). Aquí aprovechamos la propiedad de una substring de prefijo: cuando se recorre en orden inverso, el último carácter de la substring de prefijo siempre terminará al principio de la string.
Tenga en cuenta que buscamos el prefijo solo en la primera mitad de la string debido a la restricción dada en el problema de que el prefijo y el sufijo no se superponen.
Algoritmo:
1. Mantenga dos punteros: uno que comienza al final de la string (como sufijo) y otro que comienza en el medio de la string (como prefijo)
2. Continúe disminuyendo ambos punteros siempre que coincidan y el puntero de prefijo no esté agotado (>0).
3. Cuando se produzca una discrepancia, restablezca el puntero del sufijo al final de la string y repita el paso 2.
4. Cuando el puntero de prefijo alcanza ‘-1’ (es decir, la string se agota), el sufijo/prefijo común más largo será la substring del puntero de sufijo
al final de la string. Devuelve la longitud de esta substring.
Implementación:
Python3
# Python3 program to find length # of the longest prefix which # is also suffix # Returns length of the longest prefix # which is also suffix and the two do # not overlap. def longestPrefixSuffix(s): n = len(s) if n == 0: return 0 # end_suffix and end_prefix are used to keep track of the common suffix and prefix respectively. # For the prefix we search only in first half of string (0-->n//2-1) since # suffix and prefix do not overlap. end_suffix = n-1 end_prefix = n // 2 - 1 # Traverse each character of suffix from end to start and check for a match of prefix # in first half of array. while end_prefix >= 0: if s[end_prefix] != s[end_suffix]: if end_suffix != n-1: end_suffix = n-1 # reset end_suffix else: end_prefix -= 1 else: end_suffix -= 1 end_prefix -= 1 # The longest common suffix and prefix is s[end+1:] return n-end_suffix-1 # Driver Code if __name__ == "__main__": s = "ABCABCABCABCABC" print(longestPrefixSuffix(s)) # This code is contributed by Reshma Koshy.
Producción
6
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA