每日算法 — 使用java实现后缀数组：字符串高效索引与最长公共前缀

后缀数组（Suffix Array）是一种将字符串所有后缀按字典序排序后形成的整数数组，记录每个后缀在原始字符串中的起始位置。由Manber和Myers于1990年提出，后缀数组以O(n log n)的构建时间和O(n)的空间复杂度，提供了与后缀树相当的功能，同时实现更加简洁、内存更加高效。后缀数组被广泛应用于生物信息学（DNA序列比对）、文本检索、数据压缩和字符串匹配等领域。

核心思想

对于字符串S = “banana”，其所有后缀为：
– 0: banana
– 1: anana
– 2: nana
– 3: ana
– 4: na
– 5: a

按字典序排序后得到后缀数组SA = [5, 3, 1, 0, 4, 2]，表示排序后第i个后缀在原串中的起始位置。

配合最长公共前缀数组LCP（Longest Common Prefix），后缀数组可以高效解决大量字符串问题。

倍增算法构建后缀数组

倍增算法是构建后缀数组的经典方法，时间复杂度O(n log n)：

1. 初始以单个字符为键排序，得到初始排名
2. 每次将排序键长度翻倍：利用前一轮的排名，以(rank[i], rank[i+k])作为双关键字排序
3. 重复直到所有后缀排名互不相同

private void buildSuffixArray(String s) {
    int n = s.length();
    int[] sa = new int[n]; // 后缀数组
    int[] rank = new int[n]; // 排名
    int[] temp = new int[n];

    // 初始按单个字符排序
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s.charAt(i);
    }

    // 倍增过程
    for (int k = 1; k < n; k <<= 1) {
        final int kk = k;

        // 按双关键字排序
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> {
            if (rank[a] != rank[b]) return Integer.compare(rank[a], rank[b]);
            int ra = (a + kk < n) ? rank[a + kk] : -1;
            int rb = (b + kk < n) ? rank[b + kk] : -1;
            return Integer.compare(ra, rb);
        });

        for (int i = 0; i < n; i++) sa[i] = idx[i];

        // 重新计算排名
        temp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            int prev = sa[i - 1], curr = sa[i];
            int r1a = rank[prev], r1b = rank[curr];
            int r2a = (prev + kk < n) ? rank[prev + kk] : -1;
            int r2b = (curr + kk < n) ? rank[curr + kk] : -1;
            temp[curr] = temp[prev] + (r1a != r1b || r2a != r2b ? 1 : 0);
        }

        System.arraycopy(temp, 0, rank, 0, n);
        if (rank[sa[n - 1]] == n - 1) break; // 所有排名唯一，提前结束
    }

    this.suffixArray = sa;
}

最长公共前缀数组（LCP）

LCP数组记录排序后相邻后缀的最长公共前缀长度。使用Kasai算法可在O(n)时间内构建。

private void buildLCP(String s) {
    int n = s.length();
    int[] rank = new int[n];
    for (int i = 0; i < n; i++) {
        rank[suffixArray[i]] = i;
    }

    lcp = new int[n];
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] > 0) {
            int j = suffixArray[rank[i] - 1];
            while (i + h < n && j + h < n && s.charAt(i + h) == s.charAt(j + h)) {
                h++;
            }
            lcp[rank[i]] = h;
            if (h > 0) h--;
        }
    }
}

完整可运行代码

import java.util.Arrays;

/**
 * 后缀数组实现 - 基于倍增算法
 * 构建时间复杂度: O(n log n)
 * LCP构建: O(n)
 * 空间复杂度: O(n)
 */
public class SuffixArray {

    private final String text;
    private final int[] suffixArray;
    private final int[] lcp;

    public SuffixArray(String text) {
        this.text = text;
        this.suffixArray = buildSuffixArray(text);
        this.lcp = buildLCPArray(text);
    }

    private int[] buildSuffixArray(String s) {
        int n = s.length();
        int[] sa = new int[n];
        int[] rank = new int[n];
        int[] temp = new int[n];

        // 初始按单个字符排序
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) {
            idx[i] = i;
            rank[i] = s.charAt(i);
        }
        Arrays.sort(idx, (a, b) -> Integer.compare(rank[a], rank[b]));
        for (int i = 0; i < n; i++) sa[i] = idx[i];

        // 倍增过程
        for (int k = 1; k < n; k <<= 1) {
            final int kk = k;
            Arrays.sort(idx, (a, b) -> {
                if (rank[a] != rank[b]) return Integer.compare(rank[a], rank[b]);
                int ra = (a + kk < n) ? rank[a + kk] : -1;
                int rb = (b + kk < n) ? rank[b + kk] : -1;
                return Integer.compare(ra, rb);
            });

            for (int i = 0; i < n; i++) sa[i] = idx[i];

            temp[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                int prev = sa[i - 1], curr = sa[i];
                int r1a = rank[prev], r1b = rank[curr];
                int r2a = (prev + kk < n) ? rank[prev + kk] : -1;
                int r2b = (curr + kk < n) ? rank[curr + kk] : -1;
                temp[curr] = temp[prev] + (r1a != r1b || r2a != r2b ? 1 : 0);
            }

            System.arraycopy(temp, 0, rank, 0, n);
            if (rank[sa[n - 1]] == n - 1) break;
        }

        return sa;
    }

    private int[] buildLCPArray(String s) {
        int n = s.length();
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) {
            rank[suffixArray[i]] = i;
        }

        int[] lcpArray = new int[n];
        int h = 0;
        for (int i = 0; i < n; i++) {
            if (rank[i] > 0) {
                int j = suffixArray[rank[i] - 1];
                while (i + h < n && j + h < n && s.charAt(i + h) == s.charAt(j + h)) {
                    h++;
                }
                lcpArray[rank[i]] = h;
                if (h > 0) h--;
            }
        }

        return lcpArray;
    }

    /**
     * 查找模式串在文本中的所有出现位置
     * 时间复杂度: O(m log n)
     */
    public java.util.List<Integer> search(String pattern) {
        java.util.List<Integer> results = new java.util.ArrayList<>();
        int n = text.length();
        int m = pattern.length();

        if (m > n) return results;

        // 二分查找下界
        int left = 0, right = n;
        while (left < right) {
            int mid = (left + right) / 2;
            String suffix = text.substring(suffixArray[mid], Math.min(suffixArray[mid] + m, n));
            if (suffix.compareTo(pattern) < 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int start = left;

        // 二分查找上界
        right = n;
        while (left < right) {
            int mid = (left + right) / 2;
            String suffix = text.substring(suffixArray[mid], Math.min(suffixArray[mid] + m, n));
            if (suffix.compareTo(pattern) <= 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int end = left;

        for (int i = start; i < end; i++) {
            results.add(suffixArray[i]);
        }

        return results;
    }

    /**
     * 查找最长重复子串
     */
    public String longestRepeatedSubstring() {
        int maxLen = 0;
        int pos = -1;

        for (int i = 1; i < lcp.length; i++) {
            if (lcp[i] > maxLen) {
                maxLen = lcp[i];
                pos = suffixArray[i];
            }
        }

        return maxLen > 0 ? text.substring(pos, pos + maxLen) : "";
    }

    /**
     * 查找两个字符串的最长公共子串
     */
    public static String longestCommonSubstring(String s1, String s2) {
        String combined = s1 + "#" + s2 + "$";
        SuffixArray sa = new SuffixArray(combined);

        int maxLen = 0;
        int pos = -1;
        int split = s1.length();

        for (int i = 1; i < sa.lcp.length; i++) {
            int prevPos = sa.suffixArray[i - 1];
            int currPos = sa.suffixArray[i];

            // 确保两个后缀分别来自两个不同字符串
            boolean prevInS1 = prevPos < split;
            boolean currInS1 = currPos < split;

            if (prevInS1 != currInS1 && sa.lcp[i] > maxLen) {
                maxLen = sa.lcp[i];
                pos = currPos;
            }
        }

        return maxLen > 0 ? combined.substring(pos, pos + maxLen) : "";
    }

    public void printSuffixes() {
        System.out.println("后缀数组及对应后缀:");
        for (int i = 0; i < suffixArray.length; i++) {
            System.out.printf("SA[%d]=%d, LCP=%d, suffix=%s%n", 
                i, suffixArray[i], lcp[i], 
                text.substring(suffixArray[i]));
        }
    }

    public int[] getSuffixArray() {
        return suffixArray.clone();
    }

    public int[] getLCP() {
        return lcp.clone();
    }

    public static void main(String[] args) {
        String text = "banana";
        SuffixArray sa = new SuffixArray(text);
        sa.printSuffixes();

        System.out.println("\n查找 'ana': " + sa.search("ana"));
        System.out.println("查找 'na': " + sa.search("na"));
        System.out.println("最长重复子串: " + sa.longestRepeatedSubstring());

        String s1 = "abcdef";
        String s2 = "zbcdefg";
        System.out.println("\n最长公共子串 '" + s1 + "' 和 '" + s2 + "': " 
            + longestCommonSubstring(s1, s2));
    }
}

复杂度分析

其中n为文本长度，m为模式串长度。使用更高效的SA-IS算法可将构建时间降至O(n)。

经典应用场景

• 生物信息学：DNA序列比对、基因重复片段检测、短读段映射
• 全文检索：搜索引擎的倒排索引构建、大规模文本搜索
• 数据压缩：Burrows-Wheeler变换（bzip2压缩算法核心）
• 字符串分析：最长重复子串、最长公共子串、不同子串计数
• ** plagiarism检测**：文档相似度计算与抄袭片段定位

后缀数组是字符串算法领域的基石性数据结构，理解其构建原理与应用方法对于处理大规模文本数据至关重要。