private int kmp(char[] input) {
        int T[] = new int[input.length];

        int j = 1;
        int i = 0;

        T[0] = 0;

        while (j < input.length) {
            if (input[i] == input[j]) {
                T[j] = i + 1;
                i++;
            } else {
                while (i != 0) {
                    i = T[i-1];
                    if (input[j] == input[i]) {
                        T[j] = i + 1;
                        i++;
                        break;
                    }
                }
            }
            j++;
        }
        return T[input.length - 1];
    }
Date 03/04/2016
@author Tushar Roy

How to append minimum numbers of characters in front of string to make it a palindrome.

Idea is to create a new string which is original ttring + $ + reverse of original string
Get value of suffix which is also prefix using KMP.
This part of string is good. Rest needs to be copied in the front.

Time complexity is O(n)
Space complexity is O(n)

https://leetcode.com/problems/shortest-palindrome/
src/com/interview/array/ShortestPalindrome.java