package com.interview.string;

import java.util.ArrayList;
import java.util.List;

/**
 * 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
 */
public class ZAlgorithm {

    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 {
                int k1 = k - left;
                if(Z[k1] < right - k + 1) {
                    Z[k] = Z[k1];
                } else {
                    left = k;
                    while(right < input.length && input[right] == input[right - left]) {
                        right++;
                    }
                    Z[k] = right - left;
                    right--;
                }
            }
        }
        return Z;
    }

    public List<Integer> substring(char text[], char pattern[]) {
        char newString[] = new char[text.length + pattern.length + 1];
        int i = 0;
        for(char ch : pattern) {
            newString[i] = ch;
            i++;
        }
        newString[i] = '$';
        i++;
        for(char ch : text) {
            newString[i] = ch;
            i++;
        }
        List<Integer> result = new ArrayList<>();
        int Z[] = calculateZ(newString);

        for(i = 0; i < Z.length ; i++) {
            if(Z[i] == pattern.length) {
                result.add(i - pattern.length - 1);
            }
        }
        return result;
    }

    public static void main(String args[]) {
        String text = "aaabcxyzaaaabczaaczabbaaaaaabc";
        String pattern = "aaabc";
        ZAlgorithm zAlgorithm = new ZAlgorithm();
        List<Integer> result = zAlgorithm.substring(text.toCharArray(), pattern.toCharArray());
        result.forEach(System.out::println);

        int Z[] = zAlgorithm.calculateZ("aabcaabxaaaz".toCharArray());
        for(int z : Z) {
            System.out.print(z + " ");
        }
    }


}

@@ -881,26 +881,154 @@
     
-int k1 = k - left;
+//we are operating inside box%0A                int k1 = k - left;%0A                //if value does not stretches till right bound then just copy it.
 %0A   
@@ -1118,32 +1118,82 @@
         %7D else %7B
+ //otherwise try to see if there are more matches.
 %0A               
@@ -1480,32 +1480,115 @@
 eturn Z;%0A    %7D%0A%0A
+    /**%0A     * Returns list of all indices where pattern is found in text.%0A     */%0A
     public List%3C
@@ -1596,25 +1596,28 @@
 nteger%3E 
-substring
+matchPattern
 (char te
@@ -2461,17 +2461,20 @@
 thm.
-substring
+matchPattern
 (tex
@@ -2562,154 +2562,8 @@
 ln);
-%0A%0A        int Z%5B%5D = zAlgorithm.calculateZ(%22aabcaabxaaaz%22.toCharArray());%0A        for(int z : Z) %7B%0A            System.out.print(z + %22 %22);%0A        %7D
 %0A   

update z algorithm