static int[] buildSuffixArray(String s) {
        int n = s.length();  // 空文字を含むならここで+1
        SuffixArrayEntry[] sa = new SuffixArrayEntry[n];
        int[][] pos = new int[2][n];  // pos[t][i]: s.substr(i)の位置（ランク）
        for (int i = 0; i < n; i++) {  // まず1文字だけでのランクを作成
            sa[i] = new SuffixArrayEntry();
            pos[0][i] = s.charAt(i);  // 空文字を含むならpos[0][n-1]=-1; とする
        }
        for (int t = 1, step = 1;; t ^= 1, step *= 2) {
            for (int i = 0; i < n; i++) {
                sa[i].idx = i;
                sa[i].prevPos = pos[t ^ 1][i];  // 前回の位置
                sa[i].pos = i + step < n ? pos[t ^ 1][i + step] : -1;  // 前回からstep文字だけ進んだ時の位置
            }
            Arrays.sort(sa);
            if (step * 2 >= n) break;
            // 今回のランクを更新
            for (int i = 0; i < n; i++) {
                pos[t][sa[i].idx] = (i > 0 && sa[i].compareTo(sa[i - 1]) == 0)
                        ? pos[t][sa[i - 1].idx]
                        : i;
            }
        }
        // 結果をint配列にくるんで返す
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            ret[i] = sa[i].idx;
        }
        return ret;
    }