How can I echo characters before and after a string?

What are different algorithms for converting a string into a palindrome by adding characters to the end (other than appending the reverse of the string to itself)?

• adding zero or more characters to the string. Return the minimum number of characters that you need to append to  the string to make it a palindrome. e.g  str="abab" so we need to append 'a' to the string to convert it into a palindrome. so minimum character required is 1.

• Answer:

  ExplanationTo solve this problem, we must first ask:What does an optimal solution for this problem look like given various inputs?So let's explore some examples:Input => Output ab => aba aba => aba abab => ababa cat => catac baloo => baloolab Now let's compare that to your aforementioned solution of appending the reverse string:Input => Output ab => abba aba => abaaba abab => ababbaba cat => cattac baloo => baloooolab Now we ask: how can we get to the optimal solution given your first solution?The first observation we make is this:If we remove characters from the non-optimal solution, we can always get to the optimal solution.So now we should ask, how do we identify the characters that we can remove?Well, to answer that, let's look at which characters we can remove and see if we can find any patterns.Input => Output ab => abba aba => abaaba abab => ababbaba cat => cattac baloo => baloooolab Do you notice anything interesting about the following set of characters that were candidates for removal?b, aba, bab, t, ooEach is a palindrome!  Where did each palindrome come from in the original word?  The end of the word.We further observe that each palindrome is the longest possible palindrome we can form from any suffix of the word.So that tells us enough to derive the high-level solution to the problem:We first output the word.  Then we find the longest palindrome that is a suffix of our input word (hereafter referred to as the longest palindromic suffix).  We append any characters that come before that suffix in reverse order.  Now we have our answer.For example, suppose we have the word "theme."  We first output:themeThen we find the longest suffix that is a palindrome: theme.Then we append the characters to the left of that suffix (th) in reverse order: ht.That gives us: themeht, which appears to be the optimal solution.So now what remains is the details of the algorithm.  The tricky part is finding the longest suffix of a word that is a palindrome.  Ideally, we would determine this in [math]O(n)[/math] time since that will be optimal.Unfortunately, an [math]O(n)[/math] solution isn't trivial.  There are a few ways to do it, and many of the methods are similar to string search algorithms.I'll present an approach based off of the http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm that works in [math]O(n)[/math] time.  I got the idea for this approach from http://problem-solving-notes.blogspot.com/2010/11/one-solution-of-palindromic-prefix.html.As an aside, I think the problem can also be solved in [math]O(n)[/math] time by using suffix arrays / LCP arrays.  Another approach that might work would be to compute two rolling hashes for each suffix of the input string.  The first rolling hash would be generated from the letters of the suffix in order.  The second rolling hash would be generated from the letters of the suffix in reverse order.  Then you could find the longest suffix for which both rolling hash values are the same.  The rolling hash method isn't optimal, however, since hashes are subject to collisions.So let's look at the KMP-inspired approach.  I'll assume you have a basic understanding of the Knuth-Morris-Pratt algorithm.  If not, http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm is a great read.First, let me define some terminology:A prefix of x is a substring u if x starts with u.A suffix of x is a substring u if x ends with u.A prefix u of x is called a proper prefix if u.length < x.length.A suffix u of x is called a proper suffix if u.length < x.length.A border of x is a substring that is both a proper prefix and proper suffix of x. The width of a border refers to the length of the border.If you recall the preprocessing step of the Knuth-Morris-Pratt algorithm, we compute a table that stores the width of the widest border for each prefix of the search string.For example, given the search string "nana," we have:Widest border for "n" = ""Widest border for "na" = ""Widest border for "nan" = "n"Widest border for "nana" = "na"Thus, the corresponding table (specified by T) would be:T[0] = -1T[1] = len("") = 0T[2] = len("") = 0T[3] = len("n") = 1T[4] = len("na") = 2Now, let's see if we can use this idea for our problem.  Suppose we wanted to find the longest palindromic suffix of "banana" (so we're looking to find "anana").First, let's see if we can formulate a string that, when passed to the preprocessing step, gives us useful information.We note that the current preprocessing step is concerned with comparing proper prefixes of a string to proper suffixes of a string.  Since we want to find the longest palindromic suffix, then we should formulate a string where the suffix is the longest palindrome.  If the suffix is the longest palindrome, then we will want the widest border for our string to be equal to the longest palindromic suffix.The longest palindromic suffix of "banana" is "anana."  So that means whatever string we formulate should have a prefix of "anana" and a suffix of "anana," like so:anana + ??? + ananaSince we don't know the longest palindromic suffix ahead of time, we probably won't want to modify our original word too much.  It turns out that we can get the desired result by formulating the following string:reverse(banana) + sentinel + banana = ananab$banana(Here, sentinel is a character not present in the original string.  The reason we add the sentinel in is so that the KMP preprocessing step doesn't return a border that spans both the reverse string and the original string.  Thanks for pointing out this issue in my first implementation!)Now suppose we run the KMP preprocessing step on the string "ananab$banana."  Then the longest border for the prefix of size 13 (13 is the length of the entire string) would be "anana," which also happens to be the longest palindromic suffix!Thus, T[13] would be equal to 5 (the length of "anana").So now we just find the characters of "banana" to the left of the last 5 characters, which in this case is simply: "b"We reverse that substring, again giving us: "b"We then append that to our original string: "banana" + "b" = "bananab".And that's our answer!Please let me know if you need clarification.Run-time analysisWe append the original string to our output in [math]O(n)[/math] time.We compute the reverse of the original string in [math]O(n)[/math] time.We compute the reverse + original string in [math]O(n)[/math] time.We run the KMP preprocessing step in [math]O(n)[/math] time, and thus find the longest palindromic suffix in [math]O(n)[/math] time.We append the reverse of the non-palindromic suffix characters in [math]O(n)[/math] time.Thus, the entire algorithm runs in [math]O(n)[/math] time.  It uses [math]O(n)[/math] additional space as well.Java code[Warning: for demonstration purposes only... not well-tested, not clean] public class ShortestPalindrome { public static void main(String[] args) { String word = "banana"; String shortestPalindrome = getShortestPalindrome(word); System.out.println("The shortest palindrome of " + word + " is " + shortestPalindrome + "."); } public static String getShortestPalindrome(String word) { if (word == null || word.equals("")) { return word; } char[] wordArr = word.toCharArray(); return new String(getShortestPalindrome(wordArr)); } private static char[] getShortestPalindrome(char[] word) { int len = word.length; int doublePlusSentinelLen = (len << 1) + 1; char sentinel = (char)8; char[] reversedWord = reverse(word); char[] palindromicBase = new char[doublePlusSentinelLen]; // Set palindromicBase = reversedWord + sentinel + word System.arraycopy(reversedWord, 0, palindromicBase, 0, len); palindromicBase[len] = sentinel; System.arraycopy(word, 0, palindromicBase, len + 1, len); // Compute preprocessed table int[] table = new int[doublePlusSentinelLen + 1]; computeTable(table, doublePlusSentinelLen, palindromicBase); // Generate output int longestPalindromicSuffix = Math.min(len, table[doublePlusSentinelLen]); int numCharsToAppend = len - longestPalindromicSuffix; int shortestPalindromeLen = len + numCharsToAppend; char[] shortestPalindrome = new char[shortestPalindromeLen]; for (int i = 0; i < len; i++) { shortestPalindrome[i] = word[i]; } for (int i = len, j = 0; i < shortestPalindromeLen; i++, j++) { shortestPalindrome[i] = word[numCharsToAppend - j - 1]; } return shortestPalindrome; } private static void computeTable(int[] table, int len, char[] word) { table[0] = -1; for (int i = 0; i < len; ++i) { int k = table[i]; while (k >= 0 && word[k] != word[i]) { k = table[k]; } table[i + 1] = k + 1; } } private static char[] reverse(char[] text) { int len = text.length; char[] str = new char[len]; System.arraycopy(text, 0, str, 0, len); for (int leftIndex = 0, rightIndex = len - 1; leftIndex < rightIndex; leftIndex++, rightIndex--) { swap(str, leftIndex, rightIndex); } return str; } private static void swap(char[] array, int index1, int index2) { char temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } } Example output The shortest palindrome of banana is bananab.