6.3_后缀数组.md

6.3 后缀数组

• 问题描述：在长度为数百万个字符的字符串中找出其最长重复子字符串。
• 暴力解法：将字符串中每个起始位置为 i 的子字符串与另一个起始位置为 j 的子字符串相比较，记录匹配的最长子字符串。运行时间至少是字符串长度的平方级别。

后缀排序

方法：

1. 用 Java 的substring()方法创建一个由字符串 s 的所有后缀字符串（由字符串的所有位置开始得到的后缀字符串）组成的数组；
2. 将该数组排序，最长重复子字符串会出现在数组中的相邻位置；
3. 遍历排序后的数组一遍即可在相邻元素中找到最长的公共前缀。

应用：定位字符串

通过后缀排序和二分查找，我们可以迅速在大量文本中定位某个特定的子字符串（例如使用文本编辑器或浏览网页时）。

后缀数组的 API

public class SuffixArray	说明
SuffixArray(String text)	为文本 text 构造后缀数组
int length()	文本 text 的长度
String select(int i)	后缀数组中的第 i 个元素（0 <= i <= N-1）
int index(int i)	select(i) 的索引（0 <= i <= N-1）
int lcp(int i)	select(i) 和 select(i-1) 的最长公共前缀的长度（1 <= i <= N-1）
int rank(String key)	小于键 key 的后缀数量

用例

最长重复子字符串算法的用例：

/**
 * @author huang
 * 最长重复子字符串算法的用例
 */
public class LRS {
    public static void main(String[] args) {
        String text = StdIn.readAll();
        int N = text.length();
        SuffixArray sa = new SuffixArray(text);
        String lrs = "";
        for(int i = 1; i < N; i++) {
            int length = sa.lcp(i);
            if(length > lrs.length())
                lrs = sa.select(i).substring(0, length);
        }
        StdOut.println(lrs);
    }
}

上下文的关键词的索引用例：

/**
 * @author huang
 * keyword-in-context
 * 上下文的关键词的索引用例
 */
public class KWIC {
    public static void main(String[] args) {
        In in = new In(args[0]);
        int context = Integer.parseInt(args[1]);    //  关键词的前后若干个字符
        
        String text = in.readAll().replaceAll("\\s+", " ");
        int N = text.length();
        SuffixArray sa = new SuffixArray(text);
        
        while(StdIn.hasNextLine()) {
            String q = StdIn.readLine();
            for(int i = sa.rank(q); i < N && sa.select(i).startsWith(q); i++) {
                int from = Math.max(0, sa.index(i) - context);
                int to = Math.min(N-1, from + q.length() + 2 * context);
                StdOut.println(text.substring(from, to));
            }
            StdOut.println();
        }
    }
}

代码实现

/**
 * @author huang
 * 后缀数组（初级实现）
 */
public class SuffixArray {
    private final String[] suffixes;    // 后缀数组
    private final int N;    // 字符串（和数组）的长度
    
    public SuffixArray(String s) {
        N = s.length();
        suffixes = new String[N];
        for(int i = 0; i < N; i++)
            suffixes[i] = s.substring(i);
        Quick3way.sort(suffixes);
    }
    
    public int length() {
        return N;
    }
    
    public String select(int i) {
        return suffixes[i];
    }
    
    // 后缀字符串的长度说明其起始位置
    public int index(int i) {
        return N - suffixes[i].length();
    }
    
    private static int lcp(String s, String t) {
        int N = Math.min(s.length(), t.length());
        for(int i = 0; i < N; i++)
            if(s.charAt(i) != t.charAt(i))
                return i;
        return N;
    }
    
    public int lcp(int i) {
        return lcp(suffixes[i], suffixes[i-1]);
    }
    
    public int rank(String key) {
        // 二分查找
        int lo = 0, hi = N - 1;
        while(lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(suffixes[mid]);
            if(cmp < 0)
                hi = mid - 1;
            else if(cmp > 0)
                lo = mid + 1;
            else
                return mid;
        }
        return lo;
    }
}

性能

使用三向字符串快速排序，构造长度为 N 的随机字符串的后缀数组，平均所需的空间与 N 成正比，字符比较次数与 ~2NlnN 成正比（渐近于将 N 个随机字符串排序的成本）。

改进思路

SuffixArray 的初级实现在最坏情况下性能糟糕，因为排序和查找最长重复子字符串所需的时间都可能是平方级别。

Winter 算法可以在线性时间内解决最长重复子字符串问题，其基础是构造一棵由所有后缀字符串组成的字典查找树。显然在解决许多实际问题时，该算法对空间要求较大。

Manber 算法在线性对数时间内构造后缀数组，并有一个同时完成预处理和对后缀数组排序以支持常数时间的lcp()方法。