private int[] calculateZ(char input[]) {
        int Z[] = new int[input.length];
        int left = 0;
        int right = 0;
        for(int k = 1; k < input.length; k++) {
            if(k > right) {
                left = right = k;
                while(right < input.length && input[right] == input[right - left]) {
                    right++;
                }
                Z[k] = right - left;
                right--;
            } else {
                //we are operating inside box
                int k1 = k - left;
                //if value does not stretches till right bound then just copy it.
                if(Z[k1] < right - k + 1) {
                    Z[k] = Z[k1];
                } else { //otherwise try to see if there are more matches.
                    left = k;
                    while(right < input.length && input[right] == input[right - left]) {
                        right++;
                    }
                    Z[k] = right - left;
                    right--;
                }
            }
        }
        return Z;
    }
Date 10/31/2015
@author Tushar Roy

Z algorithm to pattern matching

Time complexity - O(n + m)
Space complexity - O(n + m)

http://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/
http://www.utdallas.edu/~besp/demo/John2010/z-algorithm.htm
src/com/interview/string/ZAlgorithm.java