STRSUB - furthur optimization

general
, , ,
1

This is the link to my solution for the problem STRSUB.

The solution in the link is having time complexity of O(N + QlogN). And I am trying to solve in O(N + Q) so that each query can be solved in O(1) time. For that I am replacing the binary search in each query with preprocessed array.

Binary Search

Line 147: int pos= binarySearch(far, x, y, y);

private static int binarySearch(int[] far, int s, int e, int L){
        int mid;
        while(s<=e){
            mid= (s+e) >> 1;
            if(far[mid] > L){
                e= mid-1;
            }
            else if(far[mid] <= L){
                s= mid+1;
            }
        }
        return s-1;
    }

with pre array

            int pos= pre[y];
            if(pos < x) pos= x-1;

This pre array is calculated through following code

int[] pre= new int[N];
pre[0]= -1;
for(int i=0; i<N; i++){
    pre[far[i]]= i;
}
for(int i=1; i<N; i++){
    if(pre[i] == 0){
        pre[i]= pre[i-1];
    }
}

The purpose of binary search was to find the position between ‘x’ and ‘y’ such that far[x] <= y so is the pre storing for each of number between ‘0 to N-1’.

But there is still something missing in pre which I am unable to find out which binary Search is having
and pre not.

Most of the test cases have passed. If some one could figure out some thing would be a great help.