Class CircularSuffixArray

LabEnv/10Lab/CircularSuffixArray.java:12–105

import java.util.Arrays;

public class CircularSuffixArray {
    private String text;
    private int n;
    private int[] index;

    private final static int R = 256;

    private class CircularSuffix implements Comparable<CircularSuffix> {
        int offset;

        CircularSuffix(int i) {
            offset = i;
        }

        public int compareTo(CircularSuffix that) {
            if (that == this) return 0;
            for (int i = 0; i < n; i++) {
                if (this.charAt(i) > that.charAt(i))
                    return 1;
                else if (this.charAt(i) < that.charAt(i))
                    return -1;
            }
            return 0;
        }

        public char charAt(int i) {
            return text.charAt(i + offset);
        }
    }

    private void lsdSort(CircularSuffix[] a) {
        int sz = a.length;
        int w = n;
        CircularSuffix[] aux = new CircularSuffix[sz];

        for (int d = w - 1; d >= 0; d--) {
            // sort by key-indexed counting on dth character

            // compute frequency counts
            int[] count = new int[R + 1];
            for (int i = 0; i < sz; i++)
                count[a[i].charAt(d) + 1]++;

            // compute cumulates
            for (int r = 0; r < R; r++)
                count[r + 1] += count[r];

            // move data
            for (int i = 0; i < sz; i++)
                aux[count[a[i].charAt(d)]++] = a[i];

            // copy back
            for (int i = 0; i < sz; i++)
                a[i] = aux[i];
        }
    }

    // circular suffix array of s