O(nlogn) suffix array algo

SuffixArray.java

package dev.erdos.algo;

import java.util.Arrays;

public class SuffixArray {


	// O(n*logn) algorithm for constructing a suffix array.
	// Original source: https://cp-algorithms.com/string/suffix-array.html#toc-tgt-3
	public static int[] calculateSuffixArray(char[] s) {

		s = Arrays.copyOfRange(s, 0, s.length + 1);
		s[s.length-1] = '$';
		final int n = s.length;
		final int alphabet = 256;

		int[] p = new int[n];
		int[] c = new int[n];
		int[] cnt = new int[Math.max(alphabet, n)];
		for (int i = 0; i < n; i++)
			cnt[s[i]]++;
		for (int i = 1; i < alphabet; i++)
			cnt[i] += cnt[i - 1];
		for (int i = 0; i < n; i++)
			p[--cnt[s[i]]] = i;
		c[p[0]] = 0;
		int classes = 1;
		for (int i = 1; i < n; i++) {
			if (s[p[i]] != s[p[i - 1]]) classes++;
			c[p[i]] = classes - 1;
		}
		int[] pn = new int[n];
		int[] cn = new int[n];

		for (int h = 0; (1 << h) < n; ++h) {
			for (int i = 0; i < n; i++) {
				pn[i] = p[i] - (1 << h);
				if (pn[i] < 0) pn[i] += n;
			}

			Arrays.fill(cnt, 0, classes, 0);

			for (int i = 0; i < n; i++)
				cnt[c[pn[i]]]++;
			for (int i = 1; i < classes; i++)
				cnt[i] += cnt[i - 1];
			for (int i = n - 1; i >= 0; i--)
				p[--cnt[c[pn[i]]]] = pn[i];
			cn[p[0]] = 0;
			classes = 1;
			for (int i = 1; i < n; i++) {

				int cur1 = c[p[i]];
				int cur2 = c[(p[i] + (1 << h)) % n];

				int prev1 = c[p[i - 1]];
				int prev2 = c[(p[i - 1] + (1 << h)) % n];
				if (cur1 != prev1 || cur2 != prev2) ++classes;
				cn[p[i]] = classes - 1;
			}

			// c.swap(cn);
			int[] tmp = cn;
			cn = c;
			c = tmp;
		}

		return Arrays.copyOfRange(p, 1, p.length);
	}
}