Tag Archive: suffixarray

Суффиксный массив на Java за N*log^2(N)

public static int[] getSuffixArray(String s) {
 
    System.out.println(s);
 
    int N = s.length();
 
    int steps = Integer.bitCount(Integer.highestOneBit(N) - 1);
 
    int rank[][] = new int[steps + 1][N];
 
    for (int i = 0; i < N; i++) {
        rank[0][i] = s.charAt(i) - 'a';
    }
 
    Tuple tuples[] = new Tuple[N];
 
    for (int step = 1, cnt = 1; step <= steps; step++, cnt <<= 1) {
        for (int i = 0; i < N; i++) {
            Tuple tuple = new Tuple();
            tuple.firstHalf = rank[step - 1][i];
            tuple.secondHalf = i + cnt < N ? rank[step - 1][i + cnt] : -1;
            tuple.originalIndex = i;
 
            tuples[i] = tuple;
        }
 
        Arrays.sort(tuples);
 
        rank[step][tuples[0].originalIndex] = 0;
 
        for (int i = 1, currRank = 0; i < N; i++) {
            if(!tuples[i - 1].firstHalf.equals(tuples[i].firstHalf)
                    || tuples[i - 1].secondHalf.equals(tuples[i].secondHalf)) {
                ++currRank;
            }
            rank[step][tuples[i].originalIndex] = currRank;
        }
 
 
    }
 
    int suffixArray[] = new int[N];
 
    for (int i = 0; i < N; i++) {
        suffixArray[i] = tuples[i].originalIndex;
    }
 
    return suffixArray;
}
 
static class Tuple implements Comparable<tuple> {
    Integer originalIndex;  // хранит оригинальный индекс суффикса
    Integer firstHalf;      // хранит ранг первой половины суффикса
    Integer secondHalf;     // хранит ранг второй половины суффикса
 
 
    @Override
    public int compareTo(Tuple tuple) {
        return this.firstHalf.equals(tuple.firstHalf)
                ? this.secondHalf.compareTo(tuple.secondHalf)
                : this.firstHalf.compareTo(tuple.firstHalf);
    }
 
    @Override
    public String toString() {
        return "Tuple{" +
                "originalIndex=" + originalIndex +
                ", firstHalf=" + firstHalf +
                ", secondHalf=" + secondHalf +
                '}';
    }
}
 
</tuple>