Dada la string str , la tarea es encontrar la substring palindrómica más larga formada por la concatenación del prefijo y el sufijo de la string dada str .
Ejemplos:
Entrada: str = “rombobinnimor”
Salida: rominnimor
Explicación:
La concatenación de la string “rombob”(prefijo) y “mor”(sufijo) es “rombobmor”, que es una string palindrómica.
La concatenación de la string «rom» (prefijo) e «innimor» (sufijo) es «rominnimor», que es una string palindrómica.
Pero la longitud de “rominnimor” es mayor que la de “rombobmor”.
Por lo tanto, «rominnimor» es la string requerida.Entrada: str = “geekinakeeg”
Salida: geekakeeg
Explicación:
La concatenación de la string “geek” (prefijo) y “akeeg” (sufijo) es “geekakeeg”, que es una string palindrómica.
La concatenación de la string «geeki» (prefijo) y «keeg» (sufijo) es «geekigeek», que es una string palindrómica.
Pero la longitud de «geekakeeg» es igual a «geekikeeg».
Por lo tanto, cualquiera de las strings anteriores es la string requerida.
Enfoque: la idea es utilizar el algoritmo KMP para encontrar el prefijo adecuado más largo, que es un palíndromo del sufijo de la string dada str en tiempo O(N).
- Encuentre el prefijo más largo (digamos s[0, l] ) que también es un palíndromo del sufijo (digamos s[nl, n-1] ) de la string str. El prefijo y el sufijo no se superponen.
- De la substring restante ( s[l+1, nl-1] ), encuentre la substring palindrómica más larga (por ejemplo, ans ), que es un sufijo o un prefijo de la string restante.
- La concatenación de s[0, l] , ans y s[nl, nl-1] es la substring palindrómica más larga.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function used to calculate the longest prefix
// which is also a suffix
int kmp(string s)
{
vector<int> lps(s.size(), 0);
// Traverse the string
for (int i = 1; i < s.size(); i++) {
int previous_index = lps[i - 1];
while (previous_index > 0
&& s[i] != s[previous_index]) {
previous_index = lps[previous_index - 1];
}
// Update the lps size
lps[i] = previous_index
+ (s[i] == s[previous_index] ? 1 : 0);
}
// Returns size of lps
return lps[lps.size() - 1];
}
// Function to calculate the length of longest
// palindromic substring which is either a
// suffix or prefix
int remainingStringLongestPallindrome(string s)
{
// Append a character to separate the string
// and reverse of the string
string t = s + "?";
// Reverse the string
reverse(s.begin(), s.end());
// Append the reversed string
t += s;
return kmp(t);
}
// Function to find the Longest palindromic
// string formed from concatenation of prefix
// and suffix of a given string
string longestPrefixSuffixPallindrome(string s)
{
int length = 0;
int n = s.size();
// Calculating the length for which prefix
// is reverse of suffix
for (int i = 0, j = n - 1; i < j; i++, j--) {
if (s[i] != s[j]) {
break;
}
length++;
}
// Append prefix to the answer
string ans = s.substr(0, length);
// Store the remaining string
string remaining = s.substr(length,
(n - (2 * length)));
// If the remaining string is not empty
// that means that there can be a palindrome
// substring which can be added between the
// suffix & prefix
if (remaining.size()) {
// Calculate the length of longest prefix
// palindromic substring
int longest_prefix
= remainingStringLongestPallindrome(remaining);
// Reverse the given string to find the
// longest palindromic suffix
reverse(remaining.begin(), remaining.end());
// Calculate the length of longest prefix
// palindromic substring
int longest_suffix
= remainingStringLongestPallindrome(remaining);
// If the prefix palindrome is greater
// than the suffix palindrome
if (longest_prefix > longest_suffix) {
reverse(remaining.begin(), remaining.end());
// Append the prefix to the answer
ans += remaining.substr(0, longest_prefix);
}
// If the suffix palindrome is greater than
// the prefix palindrome
else {
// Append the suffix to the answer
ans += remaining.substr(0, longest_suffix);
}
}
// Finally append the suffix to the answer
ans += s.substr(n - length, length);
// Return the answer string
return ans;
}
// Driver Code
int main()
{
string str = "rombobinnimor";
cout << longestPrefixSuffixPallindrome(str)
<< endl;
}
Python3
# Python3 implementation of # the above approach # Function used to calculate # the longest prefix # which is also a suffix def kmp(s): lps = [0] * (len(s)) # Traverse the string for i in range (1 , len(s)): previous_index = lps[i - 1] while (previous_index > 0 and s[i] != s[previous_index]): previous_index = lps[previous_index - 1] # Update the lps size lps[i] = previous_index if (s[i] == s[previous_index]): lps[i] += 1 # Returns size of lps return lps[- 1] # Function to calculate the length of # longest palindromic substring which # is either a suffix or prefix def remainingStringLongestPallindrome(s): # Append a character to separate # the string and reverse of the string t = s + "?" # Reverse the string s = s[: : -1] # Append the reversed string t += s return kmp(t) # Function to find the Longest # palindromic string formed from # concatenation of prefix # and suffix of a given string def longestPrefixSuffixPallindrome(s): length = 0 n = len(s) # Calculating the length # for which prefix # is reverse of suffix i = 0 j = n - 1 while i < j: if (s[i] != s[j]): break i += 1 j -= 1 length += 1 # Append prefix to the answer ans = s[0 : length] # Store the remaining string remaining = s[length : length + (n - (2 * length))] # If the remaining string is not empty # that means that there can be a palindrome # substring which can be added between the # suffix & prefix if (len(remaining)): # Calculate the length of longest prefix # palindromic substring longest_prefix = remainingStringLongestPallindrome(remaining); # Reverse the given string to find the # longest palindromic suffix remaining = remaining[: : -1] # Calculate the length of longest prefix # palindromic substring longest_suffix = remainingStringLongestPallindrome(remaining); # If the prefix palindrome is greater # than the suffix palindrome if (longest_prefix > longest_suffix): remaining = remaining[: : -1] # Append the prefix to the answer ans += remaining[0 : longest_prefix] # If the suffix palindrome is # greater than the prefix palindrome else: # Append the suffix to the answer ans += remaining[0 : longest_suffix] # Finally append the suffix to the answer ans += s[n - length : n] # Return the answer string return ans # Driver Code if __name__ == "__main__": st = "rombobinnimor" print (longestPrefixSuffixPallindrome(st)) # This code is contributed by Chitranayal
Javascript
<script>
// JavaScript implementation of
// the above approach
// Function used to calculate
// the longest prefix
// which is also a suffix
function kmp(s){
let lps = new Array(s.length).fill(0)
// Traverse the string
for(let i = 1; i < s.length; i++){
let previous_index = lps[i - 1]
while (previous_index > 0 && s[i] != s[previous_index])
previous_index = lps[previous_index - 1]
// Update the lps size
lps[i] = previous_index
if (s[i] == s[previous_index])
lps[i] += 1
}
// Returns size of lps
return lps[lps.length-1]
}
// Function to calculate the length of
// longest palindromic substring which
// is either a suffix or prefix
function remainingStringLongestPallindrome(s){
// Append a character to separate
// the string and reverse of the string
t = s + "?"
// Reverse the string
s = s.split("").reverse().join("")
// Append the reversed string
t += s
return kmp(t)
}
// Function to find the Longest
// palindromic string formed from
// concatenation of prefix
// and suffix of a given string
function longestPrefixSuffixPallindrome(s){
let length = 0
let n = s.length
// Calculating the length
// for which prefix
// is reverse of suffix
let i = 0
let j = n - 1
while(i < j){
if (s[i] != s[j])
break
i += 1
j -= 1
length += 1
}
// Append prefix to the answer
let ans = s.substring(0,length)
// Store the remaining string
let remaining = s.substring(length,length + (n - (2 * length)))
// If the remaining string is not empty
// that means that there can be a palindrome
// substring which can be added between the
// suffix & prefix
if(remaining.length){
// Calculate the length of longest prefix
// palindromic substring
longest_prefix = remainingStringLongestPallindrome(remaining);
// Reverse the given string to find the
// longest palindromic suffix
remaining = remaining.split("").reverse().join("")
// Calculate the length of longest prefix
// palindromic substring
longest_suffix = remainingStringLongestPallindrome(remaining);
// If the prefix palindrome is greater
// than the suffix palindrome
if (longest_prefix > longest_suffix){
remaining = remaining.split("").reverse().join("")
// Append the prefix to the answer
ans += remaining.substring(0,longest_prefix)
}
// If the suffix palindrome is
// greater than the prefix palindrome
else
// Append the suffix to the answer
ans += remaining.substring(0,longest_suffix)
}
// Finally append the suffix to the answer
ans += s.substring(n - length,n)
// Return the answer string
return ans
}
// Driver Code
let st = "rombobinnimor"
document.write(longestPrefixSuffixPallindrome(st))
// This code is contributed by shinjanpatra
</script>
Producción:
rominnimor
Complejidad de tiempo: O(N), donde N es la longitud de la string dada.
Espacio Auxiliar: O(N).
Publicación traducida automáticamente
Artículo escrito por mohitkumarbt2k18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA