IK.AM

Suffix Arrayのサンプルメモ。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class SuffixArray {
    private final String text;
    private final Integer[] suffix;

    public SuffixArray(String text) {
        this.text = text;
        this.suffix = new Integer[text.length()];
        build();
    }

    /** suffix arrayの構築 */
    private void build() {
        // 各文字のインデックスをいったん保存して
        for (int i = 0; i < text.length(); i++) {
            suffix[i] = Integer.valueOf(i);
        }
        // そのインデックスから始まる部分文字列が昇順になるようにソート
        Arrays.sort(suffix, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                String s1 = text.substring(o1.intValue());
                String s2 = text.substring(o2.intValue());
                return s1.compareTo(s2);
            }
        });
    }

    /** keyから始まる部分文字列をリストで返す */
    public List<String> search(String key) {
        List<String> result = new ArrayList<String>();
        int p = binarySearch(key);
        int ks = key.length();

        if (p != -1) {
            while (p < suffix.length) {
                int i = suffix[p].intValue();
                String s = text.substring(i, i + ks);
                if (s.equals(key)) {
                    result.add(text.substring(i));
                } else {
                    break;
                }
                p++;
            }
        }

        return result;
    }

    /** 先頭がkeyであるsuffixの最初の要素を返す2分探索 */
    private int binarySearch(String key) {
        int size = suffix.length;
        int l = -1;
        int u = size;
        int ks = key.length();

        while (l + 1 != u) {
            int m = (l + u) / 2;
            int t = suffix[m].intValue();
            String s = text.substring(t);
            if (ks < s.length()) {
                s = s.substring(0, ks);
            }
            int c = s.compareTo(key);
            if (c < 0) {
                l = m;
            } else {
                u = m;
            }
        }

        int p = u;
        if (p < size) {
            int t = suffix[p].intValue();
            String s = text.substring(t, t + ks);
            if (s.compareTo(key) == 0) {
                return p;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String input = "abracadabra";
        SuffixArray sa = new SuffixArray(input);
        for (String key : new String[] { "ra", "ab", "br" }) {
            System.out.println(key + " = " + sa.search(key));
        }
    }
}

実行結果

ra = [ra, racadabra]
ab = [abra, abracadabra]
br = [bra, bracadabra]

2分探索のところはこちら参照。