Given a string s, form a shortest palindrome by appending characters at the start of the string
abab = babab
Here we are going to use KMP method to get shortest palindrome.
Input : abab
Output : Shortest Palindrome : babab
Input : abc
Output : Shortest Palindrome : cbabc
Algorithm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
package com.omt.learn.algo; public class ShortestPalindrome { public static void main(String[] args) { String text = "abab";// "abc"; String newText = text + org.apache.commons.lang3.StringUtils.reverse(text); int kmp[] = generateKMPArray(newText); String shortestPalindrome = ""; for (int i = text.length(); i < newText.length() - kmp[kmp.length - 1]; i++) { shortestPalindrome += newText.charAt(i); } shortestPalindrome += text; System.out.println("Shortest Palindrome : " + shortestPalindrome); } public static int[] generateKMPArray(String s) { int a[] = new int[s.length()]; char c[] = s.toCharArray(); int i = 0; for (int j = 1; j < s.length();) { if (c[i] == c[j]) { i++; j++; a[j] = i; } else if (i != 0) { i = a[i - 1]; } else if (i == 0) { a[j] = 0; j++; } } return a; } } |