Given string str, the task is to find the longest palindromic substring formed by the concatenation of the prefix and suffix of the given string str.
Examples:
Input: str = “rombobinnimor”
Output: rominnimor
Explanation:
The concatenation of string “rombob”(prefix) and “mor”(suffix) is “rombobmor” which is a palindromic string.
The concatenation of string “rom”(prefix) and “innimor”(suffix) is “rominnimor” which is a palindromic string.
But the length of “rominnimor” is greater than “rombobmor”.
Therefore, “rominnimor” is the required string.Input: str = “geekinakeeg”
Output: geekakeeg
Explanation:
The concatenation of string “geek”(prefix) and “akeeg”(suffix) is “geekakeeg” which is a palindromic string.
The concatenation of string “geeki”(prefix) and “keeg”(suffix) is “geekigeek” which is a palindromic string.
But the length of “geekakeeg” is equals to “geekikeeg”.
Therefore, any of the above string is the required string.
Approach: The idea is to use KMP Algorithm to find the longest proper prefix which is a palindrome of the suffix of the given string str in O(N) time.
- Find the longest prefix(say s[0, l]) which is also a palindrome of the suffix(say s[n-l, n-1]) of the string str. Prefix and Suffix don’t overlap.
- Out of the remaining substring(s[l+1, n-l-1]), find the longest palindromic substring(say ans) which is either a suffix or prefix of the remaining string.
- The concatenation of s[0, l], ans and s[n-l, n-l-1] is the longest palindromic substring.
Below is the implementation of the above approach:
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 suffixint 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 prefixint 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 stringstring 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 Codeint main(){ string str = "rombobinnimor"; cout << longestPrefixSuffixPallindrome(str) << endl;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.lang.*;import java.util.*;class GFG { static String makeReverse(String str) { StringBuffer s = new StringBuffer(str); str = s.reverse().toString(); String[] rev = str.split(" "); StringBuffer reverse = new StringBuffer(); for (int i = rev.length - 1; i >= 0; i--) { reverse.append(rev[i]).append(" "); } return reverse.toString(); } static int kmp(String s) { int[] lps = new int[s.length()]; for (int i = 1; i < s.length(); i++) { int previous_index = lps[i - 1]; while (previous_index > 0 && s.charAt(i) != s.charAt(previous_index)) { previous_index = lps[previous_index - 1]; } lps[i] = previous_index + (s.charAt(i) == s.charAt(previous_index) ? 1 : 0); } return lps[lps.length - 1]; } static int remainingStringLongestPallindrome(String s) { String t = s + "?"; String reversed = new StringBuilder(s).reverse().toString(); t += reversed; return kmp(t); } static String longestPrefixSuffixPallindrome(String s) { int length = 0; int n = s.length(); for (int i = 0, j = n - 1; i < j; i++, j--) { if (s.charAt(i) != s.charAt(j)) { break; } length++; } String ans = s.substring(0, length); String remaining = s.substring(length, (n - length)); if (remaining.length() > 0) { int longest_prefix = remainingStringLongestPallindrome( remaining); remaining = new StringBuilder(remaining) .reverse() .toString(); int longest_suffix = remainingStringLongestPallindrome( remaining); if (longest_prefix > longest_suffix) { ans += remaining.substring(0, longest_prefix); } else { ans += remaining.substring(0, longest_suffix); } } ans += s.substring(n - length); return ans; } public static void main(String[] args) { String str = "rombobinnimor"; System.out.println( longestPrefixSuffixPallindrome(str)); }}// This code is contributed by Shivam Tiwari |
Python3
# Python3 implementation of # the above approach# Function used to calculate # the longest prefix# which is also a suffixdef 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 prefixdef 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 stringdef 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 Codeif __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 suffixfunction 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 prefixfunction 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 stringfunction 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 Codelet st = "rombobinnimor"document.write(longestPrefixSuffixPallindrome(st)) // This code is contributed by shinjanpatra</script> |
C#
using System;using System.Collections.Generic;using System.Linq;// Function used to calculate the longest prefix// which is also a suffixnamespace LongestPrefixSuffixPallindrome{ class Program { static int KMP(string s) { List<int> lps = new List<int>(new int[s.Length]); for (int i = 1; i < s.Length; i++) { int previousIndex = lps[i - 1]; while (previousIndex > 0 && s[i] != s[previousIndex]) { previousIndex = lps[previousIndex - 1]; } lps[i] = previousIndex + (s[i] == s[previousIndex] ? 1 : 0); } return lps[lps.Count - 1]; } // Function to calculate the length of longest // palindromic substring which is either a // suffix or prefix static int RemainingStringLongestPallindrome(string s) { string t = s + "?"; string reverse = new string(s.Reverse().ToArray()); t += reverse; return KMP(t); } // Function to find the Longest palindromic // string formed from concatenation of prefix // and suffix of a given string static string LongestPrefixSuffixPallindrome(string s) { int length = 0; int n = s.Length; for (int i = 0, j = n - 1; i < j; i++, j--) { if (s[i] != s[j]) { break; } length++; } string ans = s.Substring(0, length); string remaining = s.Substring(length, n - (2 * length)); if (remaining.Length > 0) { int longestPrefix = RemainingStringLongestPallindrome(remaining); string reverse = new string(remaining.Reverse().ToArray()); int longestSuffix = RemainingStringLongestPallindrome(reverse); if (longestPrefix > longestSuffix) { ans += remaining.Substring(0, longestPrefix); } else { ans += reverse.Substring(0, longestSuffix); } } ans += s.Substring(n - length, length); return ans; } static void Main(string[] args) { string str = "rombobinnimor"; Console.WriteLine(LongestPrefixSuffixPallindrome(str)); Console.ReadLine(); } }} |
Output:
rominnimor
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(N).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
