Java で Suffix Array

なんか Java で Suffix Array なコードというリクエストがあったので簡単に。
とりあえず Suffix Array の構築だけ。効率とか一切無視で。

import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class SuffixArrayBuilder {
    public void build(String text, Integer[] sa) {
        Arrays.sort(sa, new SuffixComparator(text));
    }

    private static class SuffixComparator implements Comparator<Integer> {
        private String text;

        public SuffixComparator(String text) {
            this.text = text;
        }

        @Override
        public int compare(Integer a, Integer b) {
            return text.substring(a).compareTo(text.substring(b));
        }
    }

    public static void main(String[] args) throws IOException {
        String text = "Hi Ho Hi Ho\nHi Ho\nHi";
        Integer[] sa = new Integer[text.length()];
        for (int i = 0; i < sa.length; i++) {
            sa[i] = i;
        }

        new SuffixArrayBuilder().build(text, sa);

        Pattern pat = Pattern.compile(".{0,10}");
        for (int i = 0; i < sa.length; i++) {
            Matcher m = pat.matcher(text.substring(sa[i]));
            if (m.lookingAt()) {
                System.out.printf("%3d %3d %s", i, sa[i], m.group());
                System.out.println();
            }
        }
    }
}