find(Pattern P in SuffixArray A): i = 0 lo = 0, hi = length(A) for 0<=i<length(P): Binary search for x,y where P=S[A[j]+i] for lo<=x<=j<y<=hi
lo = x, hi = y
and I am trying to get relocate it to java, but im slighty stuck. Not I can work out the simple stuff, and I have a binarysearch method, top example here (http://leepoint.net/notes-java/algorithms/searching/binarysearch.html) If possible can someone walk me through the steps in the psuedo code in the for loop?
where P=S[A[j]+i] for lo<=x<=j<y<=hi
This just says find x and y where this condition is true and implies that x and y are as far apart as possible. You are looking for suffixes in the suffix array between lo and hi where the i'th character of the suffix is equal to the i'th character of the pattern P. x is the smallest index and y is the largest index where this is true. Any j between x and y will also satisfy this condition. You could try implementing this part with a single for loop (check the condition for each j between lo and hi) first, then add a binary search.