数据结构第29节 后缀树和后缀数组

后缀树和后缀数组都是用于高效处理字符串搜索问题的数据结构，它们特别适合于解决涉及字符串模式匹配、重复子串查找等问题。下面我将结合Java代码解释这两种数据结构的基本概念以及如何构建它们。

后缀树（Suffix Tree）

后缀树是一种压缩的有根树，它的所有叶子节点代表了原字符串的所有后缀，而树的边上的标签代表了字符串的一部分。后缀树可以在线性时间内构建，并且能够在线性时间内解决许多高级字符串问题。

构建后缀树的步骤：

1. 对于每个字符位置i，从i开始创建一个新节点，并将其连接到根节点。
2. 如果路径已经存在，则沿着这个路径直到到达一个新的字符或到达一个叶节点。
3. 如果遇到新的字符，就在当前的位置创建一个新节点并将其添加到树中。
4. 如果遇到叶节点，则创建一个新的叶节点并将其添加到树中。

Java代码实现后缀树：

public class SuffixTree {
    private class Node {
        Map<Character, Node> links;
        boolean endOfWord;

        Node() {
            links = new HashMap<>();
            endOfWord = false;
        }
    }

    private Node root;
    private String text;

    public SuffixTree(String text) {
        this.text = text + "$";
        root = new Node();
        for (int i = 0; i < text.length(); i++) {
            insertSuffix(i);
        }
    }

    private void insertSuffix(int i) {
        Node node = root;
        while (i < text.length()) {
            char currentChar = text.charAt(i);
            if (!node.links.containsKey(currentChar)) {
                node.links.put(currentChar, new Node());
            }
            node = node.links.get(currentChar);
            i++;
        }
        node.endOfWord = true;
    }
}

请注意，这只是一个简化的后缀树实现，未考虑压缩路径和共享子树等优化，实际应用中通常会使用更复杂的数据结构和算法，例如Ukkonen的线性时间算法。

后缀数组（Suffix Array）

后缀数组是一个整数数组，它包含了源字符串所有后缀的起始索引，按照字典序排序。后缀数组比后缀树占用的空间少，但某些操作可能不如后缀树快。

构建后缀数组的步骤：

1. 计算所有后缀。
2. 将所有后缀按字典序排序。
3. 存储排序后的后缀的起始索引。

Java代码实现后缀数组：

public class SuffixArray {
    private int[] array;
    private String text;

    public SuffixArray(String text) {
        this.text = text;
        array = new int[text.length()];
        for (int i = 0; i < text.length(); i++) {
            array[i] = i;
        }
        Arrays.sort(array, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return text.substring(o1).compareTo(text.substring(o2));
            }
        });
    }

    public int[] getArray() {
        return array;
    }
}

这个实现使用了Java的Arrays.sort()方法来排序后缀，但是由于substring()的时间复杂度是O(n)，整体的排序时间复杂度会大于O(n log n)，在实际应用中，通常会使用更高效的排序算法，如基于计数的排序算法（如DC3算法）。

以上是后缀树和后缀数组的基本介绍和简单的Java实现。在实际项目中，这两种数据结构都有各自的优点和应用场景，选择使用哪种取决于具体的需求和性能考量。

在之前的讨论中，我们已经概述了后缀树和后缀数组的基本结构和构造方法。现在，让我们进一步完善这两个数据结构的实现，增加一些实用功能，比如查找模式在字符串中的位置，以及在后缀数组中实现二分查找。

扩展后缀树的功能

查找模式

我们可以通过遍历后缀树来查找一个模式在字符串中的所有出现位置。

public List<Integer> findPattern(String pattern) {
    List<Integer> positions = new ArrayList<>();
    Node node = root;
    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i);
        if (node.links.containsKey(c)) {
            node = node.links.get(c);
        } else {
            return positions; // 模式不存在
        }
    }
    findLeaves(node, positions); // 找到模式后，收集所有叶子节点的索引
    return positions;
}

private void findLeaves(Node node, List<Integer> positions) {
    if (node.endOfWord) {
        positions.add(text.indexOf(node.text)); // 这里简化了，需要根据实际的节点结构计算索引
    }
    for (Character c : node.links.keySet()) {
        findLeaves(node.links.get(c), positions);
    }
}

扩展后缀数组的功能

二分查找模式

后缀数组有序的特点允许我们使用二分查找来高效地定位模式。

public List<Integer> findPatternInSuffixArray(String pattern) {
    List<Integer> positions = new ArrayList<>();
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int comparison = text.substring(array[mid]).compareTo(pattern);
        if (comparison < 0) {
            left = mid + 1;
        } else if (comparison > 0) {
            right = mid - 1;
        } else {
            findPatternRange(mid, pattern, positions);
            break;
        }
    }
    return positions;
}

private void findPatternRange(int mid, String pattern, List<Integer> positions) {
    int left = mid, right = mid;
    while (left >= 0 && text.substring(array[left]).equals(pattern)) {
        positions.add(array[left]);
        left--;
    }
    while (right < array.length && text.substring(array[right]).equals(pattern)) {
        positions.add(array[right]);
        right++;
    }
}

请注意，上述代码中的某些部分进行了简化处理，例如在后缀树中确定模式出现的具体位置需要根据实际的节点结构来计算，而在后缀数组中，查找范围的确定也需要更精确的逻辑来避免超出边界。

完善的后缀树和后缀数组代码

考虑到实际应用的复杂性，下面的代码片段提供了更完整、更准确的实现，包括了模式查找的细节处理：

public class SuffixTree {
    // ... 之前的代码 ...

    public List<Integer> findPattern(String pattern) {
        List<Integer> positions = new ArrayList<>();
        Node node = root;
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (node.links.containsKey(c)) {
                node = node.links.get(c);
            } else {
                return positions; // 模式不存在
            }
        }
        collectPositions(node, positions);
        return positions;
    }

    private void collectPositions(Node node, List<Integer> positions) {
        if (node.endOfWord) {
            positions.add(node.startIndex); // 根据节点记录的开始索引
        }
        for (Character c : node.links.keySet()) {
            collectPositions(node.links.get(c), positions);
        }
    }
}

public class SuffixArray {
    // ... 之前的代码 ...

    public List<Integer> findPattern(String pattern) {
        List<Integer> positions = new ArrayList<>();
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int comparison = text.substring(array[mid]).compareTo(pattern);
            if (comparison < 0) {
                left = mid + 1;
            } else if (comparison > 0) {
                right = mid - 1;
            } else {
                findPatternRange(mid, pattern, positions);
                break;
            }
        }
        return positions;
    }

    private void findPatternRange(int mid, String pattern, List<Integer> positions) {
        int left = mid, right = mid;
        while (left >= 0 && text.substring(array[left], array[left] + pattern.length()).equals(pattern)) {
            positions.add(array[left]);
            left--;
        }
        while (right < array.length && text.substring(array[right], array[right] + pattern.length()).equals(pattern)) {
            positions.add(array[right]);
            right++;
        }
    }
}

这些代码片段提供了基本的框架和功能，但在实际应用中，可能需要进一步的调试和优化，以适应不同的字符串长度和模式查找需求。