package strings;

import java.util.*;

import java.util.stream.IntStream;

// https://en.wikipedia.org/wiki/Suffix_array

public class SuffixArray2 {

// suffix array in O(n*log^2(n))

public static int[] suffixArray(CharSequence s) {

int n = s.length();

Integer[] sa = IntStream.range(0, n).boxed().toArray(Integer[] ::new);

int[] rank = s.chars().toArray();

for (int len = 1; len < n; len *= 2) {

long[] rank2 = new long[n];

for (int i = 0; i < n; i++) rank2[i] = ((long) rank[i] << 32) + (i + len < n ? rank[i + len] + 1 : 0);

Arrays.sort(sa, Comparator.comparingLong(a -> rank2[a]));

for (int i = 0; i < n; i++) rank[sa[i]] = i > 0 && rank2[sa[i - 1]] == rank2[sa[i]] ? rank[sa[i - 1]] : i;

}

return Arrays.stream(sa).mapToInt(Integer::intValue).toArray();

}

// random test

public static void main(String[] args) {

Random rnd = new Random(1);

for (int step = 0; step < 100000; step++) {

int n = rnd.nextInt(100);

StringBuilder s = rnd.ints(n, 0, 10).collect(

StringBuilder::new, (sb, i) -> sb.append((char) ('a' + i)), StringBuilder::append);

int[] sa = suffixArray(s);

for (int i = 0; i + 1 < n; i++)

if (s.substring(sa[i]).compareTo(s.substring(sa[i + 1])) >= 0)

throw new RuntimeException();

}

System.out.println("Test passed");

}

}