---
title: 接尾辞配列(Suffix Array)
tags: []
categories: ["Programming", "DataStructure", "SuffixArray"]
date: 2011-07-22T14:06:09Z
updated: 2011-07-22T14:06:09Z
---

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分探索のところは[こちら][1]参照。


  [1]: http://blog.ik.am/entry/view/id/68/title/%E6%9C%80%E5%88%9D%E3%81%AE%E8%A6%81%E7%B4%A0%E3%82%92%E8%BF%94%E3%81%99%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2/