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>
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.