Shortest Palindrome

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
Solution:
1. public class Solution {
2. public String shortestPalindrome(String s) {
3. String r = new StringBuilder(s).reverse().toString();
4. int[] lps = getLPS(s + '|' + r);
5. return r.substring(0, r.length() - lps[lps.length - 1]) + s;
6. }
7. 8. // KMP get longest prefix and suffix count
9. int[] getLPS(String s) {
10. int[] lps = new int[s.length()];
11. int i = 1, len = 0;
12. 13. while (i < s.length()) {
14. if (s.charAt(i) == s.charAt(len)) lps[i++] = ++len;
15. else if (len == 0) lps[i++] = 0;
16. else len = lps[len - 1];
17. }
18. 19. return lps;
20. }
21. }