Print the longest palindromic prefix of a given string
Given a string str, the task is to find the longest palindromic prefix of the given string.
Examples:
Input: str = “abaac”
Output: aba
Explanation:
The longest prefix of the given string which is palindromic is “aba”.Input: str = “abacabaxyz”
Output: abacaba
Explanation:
The prefixes of the given string which is palindromic are “aba” and “abacabaxyz”.
But the longest of among two is “abacabaxyz”.
Naive Approach: The idea is to generate all the substring of the given string from the starting index and check whether the substrings are palindromic or not. The palindromic string with a maximum length is the resultant string.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the longest prefix // which is palindromic void LongestPalindromicPrefix(string s) { // Find the length of the given string int n = s.length(); // For storing the length of longest // prefix palindrome int max_len = 0; // Loop to check the substring of all // length from 1 to N which is palindrome for ( int len = 1; len <= n; len++) { // String of length i string temp = s.substr(0, len); // To store the reversed of temp string temp2 = temp; // Reversing string temp2 reverse(temp2.begin(), temp2.end()); // If string temp is palindromic // then update the length if (temp == temp2) { max_len = len; } } // Print the palindromic string of // max_len cout << s.substr(0, max_len); } // Driver Code int main() { // Given string string str = "abaab" ; // Function Call LongestPalindromicPrefix(str); } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the longest prefix // which is palindromic static void LongestPalindromicPrefix(String s) { // Find the length of the given String int n = s.length(); // For storing the length of longest // prefix palindrome int max_len = 0 ; // Loop to check the subString of all // length from 1 to N which is palindrome for ( int len = 1 ; len <= n; len++) { // String of length i String temp = s.substring( 0 , len); // To store the reversed of temp String temp2 = temp; // Reversing String temp2 temp2 = reverse(temp2); // If String temp is palindromic // then update the length if (temp.equals(temp2)) { max_len = len; } } // Print the palindromic String of // max_len System.out.print(s.substring( 0 , max_len)); } static String reverse(String input) { char [] a = input.toCharArray(); int l, r = a.length - 1 ; for (l = 0 ; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a); } // Driver Code public static void main(String[] args) { // Given String String str = "abaab" ; // Function Call LongestPalindromicPrefix(str); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach # Function to find the longest prefix # which is palindrome def LongestPalindromicPrefix(string): # Find the length of the given string n = len (string) # For storing the length of longest # Prefix Palindrome max_len = 0 # Loop to check the substring of all # length from 1 to n which is palindrome for length in range ( 0 , n + 1 ): # String of length i temp = string[ 0 :length] # To store the value of temp temp2 = temp # Reversing the value of temp temp3 = temp2[:: - 1 ] # If string temp is palindromic # then update the length if temp = = temp3: max_len = length # Print the palindromic string # of max_len print (string[ 0 :max_len]) # Driver code if __name__ = = '__main__' : string = "abaac" ; # Function call LongestPalindromicPrefix(string) # This code is contributed by virusbuddah_ |
C#
// C# program for the above approach using System; class GFG{ // Function to find the longest prefix // which is palindromic static void longestPalindromicPrefix(String s) { // Find the length of the given String int n = s.Length; // For storing the length of longest // prefix palindrome int max_len = 0; // Loop to check the subString of all // length from 1 to N which is palindrome for ( int len = 1; len <= n; len++) { // String of length i String temp = s.Substring(0, len); // To store the reversed of temp String temp2 = temp; // Reversing String temp2 temp2 = reverse(temp2); // If String temp is palindromic // then update the length if (temp.Equals(temp2)) { max_len = len; } } // Print the palindromic String of // max_len Console.Write(s.Substring(0, max_len)); } static String reverse(String input) { char [] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join( "" ,a); } // Driver Code public static void Main(String[] args) { // Given String String str = "abaab" ; // Function Call longestPalindromicPrefix(str); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // JavaScript program for the above approach // Function to find the longest prefix // which is palindromic function LongestPalindromicPrefix(s) { // Find the length of the given String let n = s.length; // For storing the length of longest // prefix palindrome let max_len = 0; // Loop to check the subString of all // length from 1 to N which is palindrome for (let len = 1; len <= n; len++) { // String of length i let temp = s.substring(0, len); // To store the reversed of temp let temp2 = temp; // Reversing String temp2 temp2 = reverse(temp2); // If String temp is palindromic // then update the length if (temp == temp2) { max_len = len; } } // Print the palindromic String of // max_len document.write(s.substring(0, max_len)); } function reverse(input) { let a = input.split( '' ); let l, r = a.length - 1; for (l = 0; l < r; l++, r--) { let temp = a[l]; a[l] = a[r]; a[r] = temp; } return a.join( "" ); } // Given String let str = "abaab" ; // Function Call LongestPalindromicPrefix(str); </script> |
aba
Time Complexity: O(N2), where N is the length of the given string.
Efficient Approach: The idea is to use preprocessing algorithm KMP Algorithm. Below are the steps:
- Create a temporary string(say str2) which is:
str2 = str + '?' reverse(str);
- Create an array(say lps[]) of size of length of the string str2 which will store the longest palindromic prefix which is also a suffix of string str2.
- Update the lps[] by using preprocessing algorithm of KMP Search Algorithm.
- lps[length(str2) – 1] will give the length of the longest palindromic prefix string of the given string str.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the longest prefix // which is palindromic void LongestPalindromicPrefix(string str) { // Create temporary string string temp = str + '?' ; // Reverse the string str reverse(str.begin(), str.end()); // Append string str to temp temp += str; // Find the length of string temp int n = temp.length(); // lps[] array for string temp int lps[n]; // Initialise every value with zero fill(lps, lps + n, 0); // Iterate the string temp for ( int i = 1; i < n; i++) { // Length of longest prefix // till less than i int len = lps[i - 1]; // Calculate length for i+1 while (len > 0 && temp[len] != temp[i]) { len = lps[len - 1]; } // If character at current index // len are same then increment // length by 1 if (temp[i] == temp[len]) { len++; } // Update the length at current // index to len lps[i] = len; } // Print the palindromic string of // max_len cout << temp.substr(0, lps[n - 1]); } // Driver's Code int main() { // Given string string str = "abaab" ; // Function Call LongestPalindromicPrefix(str); } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the longest // prefix which is palindromic static void LongestPalindromicPrefix(String str) { // Create temporary String String temp = str + '?' ; // Reverse the String str str = reverse(str); // Append String str to temp temp += str; // Find the length of String temp int n = temp.length(); // lps[] array for String temp int []lps = new int [n]; // Initialise every value with zero Arrays.fill(lps, 0 ); // Iterate the String temp for ( int i = 1 ; i < n; i++) { // Length of longest prefix // till less than i int len = lps[i - 1 ]; // Calculate length for i+1 while (len > 0 && temp.charAt(len) != temp.charAt(i)) { len = lps[len - 1 ]; } // If character at current index // len are same then increment // length by 1 if (temp.charAt(i) == temp.charAt(len)) { len++; } // Update the length at current // index to len lps[i] = len; } // Print the palindromic String // of max_len System.out.print(temp.substring( 0 , lps[n - 1 ])); } static String reverse(String input) { char [] a = input.toCharArray(); int l, r = a.length - 1 ; for (l = 0 ; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a); } // Driver Code public static void main(String[] args) { // Given String String str = "abaab" ; // Function Call LongestPalindromicPrefix(str); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program for the above approach # Function to find the longest prefix # which is palindromic def LongestPalindromicPrefix( Str ): # Create temporary string temp = Str + "?" # Reverse the string Str Str = Str [:: - 1 ] # Append string Str to temp temp = temp + Str # Find the length of string temp n = len (temp) # lps[] array for string temp lps = [ 0 ] * n # Iterate the string temp for i in range ( 1 , n): # Length of longest prefix # till less than i Len = lps[i - 1 ] # Calculate length for i+1 while ( Len > 0 and temp[ Len ] ! = temp[i]): Len = lps[ Len - 1 ] # If character at current index # Len are same then increment # length by 1 if (temp[i] = = temp[ Len ]): Len + = 1 # Update the length at current # index to Len lps[i] = Len # Print the palindromic string # of max_len print (temp[ 0 : lps[n - 1 ]]) # Driver Code if __name__ = = '__main__' : # Given string Str = "abaab" # Function call LongestPalindromicPrefix( Str ) # This code is contributed by himanshu77 |
C#
// C# program for the above approach using System; class GFG{ // Function to find the longest // prefix which is palindromic static void longestPalindromicPrefix(String str) { // Create temporary String String temp = str + '?' ; // Reverse the String str str = reverse(str); // Append String str to temp temp += str; // Find the length of String temp int n = temp.Length; // lps[] array for String temp int []lps = new int [n]; // Iterate the String temp for ( int i = 1; i < n; i++) { // Length of longest prefix // till less than i int len = lps[i - 1]; // Calculate length for i+1 while (len > 0 && temp[len] != temp[i]) { len = lps[len - 1]; } // If character at current index // len are same then increment // length by 1 if (temp[i] == temp[len]) { len++; } // Update the length at current // index to len lps[i] = len; } // Print the palindromic String // of max_len Console.Write(temp.Substring(0, lps[n - 1])); } static String reverse(String input) { char [] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join( "" , a); } // Driver Code public static void Main(String[] args) { // Given String String str = "abaab" ; // Function Call longestPalindromicPrefix(str); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program for the above approach // Function to find the longest // prefix which is palindromic function longestPalindromicPrefix(str) { // Create temporary String let temp = str + '?' ; // Reverse the String str str = reverse(str); // Append String str to temp temp += str; // Find the length of String temp let n = temp.length; // lps[] array for String temp let lps = new Array(n); lps.fill(0); // Iterate the String temp for (let i = 1; i < n; i++) { // Length of longest prefix // till less than i let len = lps[i - 1]; // Calculate length for i+1 while (len > 0 && temp[len] != temp[i]) { len = lps[len - 1]; } // If character at current index // len are same then increment // length by 1 if (temp[i] == temp[len]) { len++; } // Update the length at current // index to len lps[i] = len; } // Print the palindromic String // of max_len document.write(temp.substring(0, lps[n - 1])); } function reverse(input) { let a = input.split( '' ); let l, r = a.length - 1; for (l = 0; l < r; l++, r--) { let temp = a[l]; a[l] = a[r]; a[r] = temp; } return a.join( "" ); } // Driver code // Given String let str = "abaab" ; // Function Call longestPalindromicPrefix(str); // This code is contributed by mukesh07 </script> |
aba
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(N), where N is the length of the given string.
Contact Us