toy example of building a suffix array and using it for efficient string search.

SuffixArray.java

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

public class SuffixArray {
    private static class Suffix {
        public int index;
        public String suffix;
        Suffix(int i, String s) {
            this.index = i;
            this.suffix = s;
        }
    }

    public static int[] buildSuffixArray(String text) {
        int N = text.length();
        List<Suffix> suffArr = new ArrayList<>();
        int[] retArr = new int[N];
        for (int i = 0; i < N; i++) {
            suffArr.add(new Suffix(i, text.substring(i)));
        }
        suffArr.sort((Suffix a, Suffix b) -> { return a.suffix.compareTo(b.suffix); });
        for (int i = 0; i < N; i++)
            retArr[i] = suffArr.get(i).index;
        return retArr;
    }


    public static void search(String text, String pat) {
        int[] arr = buildSuffixArray("banana");
        int N = arr.length;
        int l = 0;
        int r = N-1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            String substr = text.substring(arr[mid], arr[mid] + pat.length());
            int cmp = pat.compareTo(substr);
            if (cmp < 0) r = mid - 1;
            else if (cmp > 0) l = mid + 1;
            else {
                System.out.println("Found at index " + arr[mid]);
                return;
            }
        }
        System.out.println("Not found.");
    }

    public static void main(String[] args) {
        search("banana", "nan");
    }
}