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 {
//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;
}
/**
* Returns list of all indices where pattern is found in text.
*/
public List