Longest palindromic string formed by concatenation of prefix and suffix of a string

0 0 8 minutes read

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 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;
}

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

C#

using System;
using System.Collections.Generic;
using System.Linq;
// Function used to calculate the longest prefix
// which is also a suffix
namespace 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 zambiatek!