跳转至

后缀树与后缀数组

概述

后缀树（Suffix Tree）是一种紧凑的 Trie 结构，用于高效处理字符串问题。后缀数组（Suffix Array）是后缀树的空间优化版本，通过存储所有后缀的字典序排列实现相同功能，在实际应用中更为广泛。

核心应用：字符串匹配、最长重复子串、最长公共子串、回文检测、字符串压缩等。后缀数组配合 LCP 数组，可以解决大多数字符串问题。

后缀树特点

特性 说明
压缩Trie 压缩单分支路径，空间 O(n)
线性构建 Ukkonen 算法 O(n) 构建
高效查询 子串查找 O(m)
强大功能 支持多种字符串操作

后缀数组详解

后缀数组定义

对于字符串 S，后缀数组 SA 是一个整数数组，SA[i] 表示按字典序排序后第 i 个后缀的起始位置。

示例：字符串 "banana$"

所有后缀：

索引 后缀
0banana$
1anana$
2nana$
3ana$
4na$
5a$
6$

按字典序排序：

排序序号 起始索引 后缀
06$
15a$
23ana$
31anana$
40banana$
54na$
62nana$
后缀数组：SA = [6, 5, 3, 1, 0, 4, 2]

后缀数组可视化

graph LR
    subgraph 后缀数组SA
        SA0["SA[0]=6<br/>$"]
        SA1["SA[1]=5<br/>a$"]
        SA2["SA[2]=3<br/>ana$"]
        SA3["SA[3]=1<br/>anana$"]
        SA4["SA[4]=0<br/>banana$"]
        SA5["SA[5]=4<br/>na$"]
        SA6["SA[6]=2<br/>nana$"]
        
        SA0 --> SA1 --> SA2 --> SA3 --> SA4 --> SA5 --> SA6
    end
    
    style SA0 fill:#4CAF50,color:#fff
    style SA1 fill:#2196F3,color:#fff
    style SA2 fill:#2196F3,color:#fff
    style SA3 fill:#2196F3,color:#fff
    style SA4 fill:#FF9800,color:#fff
    style SA5 fill:#9C27B0,color:#fff
    style SA6 fill:#9C27B0,color:#fff

LCP 数组

LCP 定义

LCP（Longest Common Prefix）数组，LCP[i] 表示后缀 SA[i] 和 SA[i-1] 的最长公共前缀长度。

LCP 数组计算

字符串: banana$
SA: [6, 5, 3, 1, 0, 4, 2]
后缀: [$, a$, ana$, anana$, banana$, na$, nana$]
LCP[0] = 0 (第一个后缀没有前驱)
LCP[1] = LCP("$", "a$") = 0
LCP[2] = LCP("a$", "ana$") = 1 ("a")
LCP[3] = LCP("ana$", "anana$") = 3 ("ana")
LCP[4] = LCP("anana$", "banana$") = 0
LCP[5] = LCP("banana$", "na$") = 0
LCP[6] = LCP("na$", "nana$") = 2 ("na")
LCP: [0, 0, 1, 3, 0, 0, 2]

LCP 可视化

SA 后缀 LCP 公共前缀
6 $ 0 -
5 a$ 0 -
3 ana$ 1 "a"
1 anana$ 3 "ana"
0 banana$ 0 -
4 na$ 0 -
2 nana$ 2 "na"
LCP 数组的作用：LCP 数组揭示了相邻排序后缀的相似程度，是解决许多字符串问题的关键。结合后缀数组和 LCP 数组，可以高效解决最长重复子串、最长公共子串等问题。

数据结构

C
1
2
3
4
5
6
typedef struct {
    char *text;    // 原字符串
    int *sa;       // 后缀数组
    int *lcp;      // LCP 数组
    int n;         // 字符串长度
} SuffixArray;

构建后缀数组

朴素构建 O(n² log n)

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
SuffixArray* buildSuffixArrayNaive(char *text) {
    int n = strlen(text);
    
    SuffixArray *sa = (SuffixArray*)malloc(sizeof(SuffixArray));
    sa->text = strdup(text);
    sa->n = n;
    sa->sa = (int*)malloc(sizeof(int) * n);
    
    // 初始化：每个位置作为一个后缀
    for (int i = 0; i < n; i++) {
        sa->sa[i] = i;
    }
    
    // 按后缀字典序排序
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (strcmp(text + sa->sa[j], text + sa->sa[j + 1]) > 0) {
                int temp = sa->sa[j];
                sa->sa[j] = sa->sa[j + 1];
                sa->sa[j + 1] = temp;
            }
        }
    }
    
    return sa;
}

倍增算法 O(n log² n)

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int* buildSuffixArrayDC3(char *text, int n) {
    int *sa = (int*)malloc(sizeof(int) * n);
    int *rank = (int*)malloc(sizeof(int) * 2 * n);
    int *tmp = (int*)malloc(sizeof(int) * n);
    
    // 初始排名：按字符值
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = (unsigned char)text[i];
    }
    
    // 倍增排序
    for (int k = 1; k < n; k *= 2) {
        // 按二元组 (rank[i], rank[i+k]) 排序
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                int a = sa[j], b = sa[j + 1];
                int ra = rank[a], rb = rank[b];
                int rak = (a + k < n) ? rank[a + k] : -1;
                int rbk = (b + k < n) ? rank[b + k] : -1;
                
                if (ra > rb || (ra == rb && rak > rbk)) {
                    int temp = sa[j];
                    sa[j] = sa[j + 1];
                    sa[j + 1] = temp;
                }
            }
        }
        
        // 重新计算排名
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            int a = sa[i - 1], b = sa[i];
            int ra = rank[a], rb = rank[b];
            int rak = (a + k < n) ? rank[a + k] : -1;
            int rbk = (b + k < n) ? rank[b + k] : -1;
            
            tmp[b] = tmp[a] + (ra != rb || rak != rbk);
        }
        
        for (int i = 0; i < n; i++) {
            rank[i] = tmp[i];
        }
        
        // 所有排名不同，排序完成
        if (rank[sa[n - 1]] == n - 1) break;
    }
    
    free(rank);
    free(tmp);
    return sa;
}

倍增算法示意：

flowchart TD
    A["初始: 按单字符排名"]
    B["k=1: 按 rank i, rank i+1 排序"]
    C["k=2: 按 rank i, rank i+2 排序"]
    D["k=4: 按 rank i, rank i+4 排序"]
    E["..."]
    F["所有排名不同，完成"]
    
    A --> B --> C --> D --> E --> F
    
    style A fill:#E3F2FD
    style F fill:#E8F5E9

构建 LCP 数组

Kasai 算法 O(n)

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int* buildLCP(char *text, int *sa, int n) {
    int *lcp = (int*)calloc(n, sizeof(int));
    int *rank = (int*)malloc(sizeof(int) * n);
    
    // 计算 rank 数组：rank[i] 表示后缀 i 在 SA 中的位置
    for (int i = 0; i < n; i++) {
        rank[sa[i]] = i;
    }
    
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] > 0) {
            int j = sa[rank[i] - 1];  // 排名相邻的后缀
            
            // 利用之前的 h 值，从 h-1 开始比较
            while (i + h < n && j + h < n && text[i + h] == text[j + h]) {
                h++;
            }
            
            lcp[rank[i]] = h;
            if (h > 0) h--;  // 下一个后缀的 LCP 至少为 h-1
        }
    }
    
    free(rank);
    return lcp;
}
Kasai 算法关键：利用 LCP 的性质，后缀 i+1 和 j+1 的 LCP 至少为 LCP(i,j)-1，从而避免重复比较，实现 O(n) 时间构建。

子串查找

利用后缀数组二分查找

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int searchSubstring(SuffixArray *sa, char *pattern) {
    int m = strlen(pattern);
    int n = sa->n;
    
    // 找到第一个 ≥ pattern 的后缀
    int left = 0, right = n;
    while (left < right) {
        int mid = (left + right) / 2;
        if (strncmp(sa->text + sa->sa[mid], pattern, m) < 0) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    int start = left;
    
    // 找到第一个 > pattern 的后缀
    right = n;
    while (left < right) {
        int mid = (left + right) / 2;
        if (strncmp(sa->text + sa->sa[mid], pattern, m) <= 0) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    // 出现次数 = right - start
    return right - start;
}

查找示例：

字符串: banana$
模式: "ana"
SA: [6, 5, 3, 1, 0, 4, 2]
后缀: [$, a$, ana$, anana$, banana$, na$, nana$]
二分查找 "ana":
找到第一个 ≥ "ana": SA[2]=3 (ana$)
找到第一个 > "ana": SA[4]=0 (banana$)
出现次数 = 4 - 2 = 2
匹配位置: SA[2]=3, SA[3]=1
即 "ana" 出现在位置 3 和位置 1

最长公共子串

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
char* longestCommonSubstring(char *s1, char *s2) {
    int n1 = strlen(s1);
    int n2 = strlen(s2);
    
    // 拼接两个字符串，用特殊字符分隔
    char *combined = (char*)malloc(n1 + n2 + 2);
    sprintf(combined, "%s#%s", s1, s2);
    
    int n = n1 + n2 + 1;
    int *sa = buildSuffixArrayDC3(combined, n);
    int *lcp = buildLCP(combined, sa, n);
    
    int maxLen = 0;
    int maxIndex = 0;
    
    // 找到最大的 LCP，且两个后缀来自不同字符串
    for (int i = 1; i < n; i++) {
        int j1 = sa[i - 1];
        int j2 = sa[i];
        
        // 一个来自 s1，一个来自 s2
        if ((j1 < n1 && j2 > n1) || (j1 > n1 && j2 < n1)) {
            if (lcp[i] > maxLen) {
                maxLen = lcp[i];
                maxIndex = sa[i];
            }
        }
    }
    
    char *result = (char*)malloc(maxLen + 1);
    strncpy(result, combined + maxIndex, maxLen);
    result[maxLen] = '\0';
    
    free(combined);
    free(sa);
    free(lcp);
    
    return result;
}

最长公共子串示意：

s1 = "banana"
s2 = "canada"
拼接: "banana#canada"
找到来自不同字符串的后缀对的最大 LCP:
"ana" (来自 s1 位置 1 和 3)
"ana" (来自 s2 位置 1)
最长公共子串: "ana" (长度 3)

C++ 实现

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <vector>
#include <string>
#include <algorithm>

class SuffixArray {
private:
    std::string text;
    std::vector<int> sa;
    std::vector<int> lcp;
    std::vector<int> rank;
    int n;
    
public:
    SuffixArray(const std::string& s) : text(s), n(s.length()) {
        sa.resize(n);
        lcp.resize(n);
        rank.resize(n);
        buildSA();
        buildLCP();
    }
    
    void buildSA() {
        for (int i = 0; i < n; i++) sa[i] = i;
        for (int i = 0; i < n; i++) rank[i] = text[i];
        
        std::vector<int> tmp(n);
        for (int k = 1; k < n; k *= 2) {
            auto cmp = [&](int a, int b) {
                if (rank[a] != rank[b]) return rank[a] < rank[b];
                int ra = (a + k < n) ? rank[a + k] : -1;
                int rb = (b + k < n) ? rank[b + k] : -1;
                return ra < rb;
            };
            
            std::sort(sa.begin(), sa.end(), cmp);
            
            tmp[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
            }
            rank = tmp;
            
            if (rank[sa[n - 1]] == n - 1) break;
        }
    }
    
    void buildLCP() {
        for (int i = 0; i < n; i++) rank[sa[i]] = i;
        
        int h = 0;
        for (int i = 0; i < n; i++) {
            if (rank[i] > 0) {
                int j = sa[rank[i] - 1];
                while (i + h < n && j + h < n && text[i + h] == text[j + h]) h++;
                lcp[rank[i]] = h;
                if (h > 0) h--;
            }
        }
    }
    
    int countOccurrences(const std::string& pattern) {
        int m = pattern.length();
        
        int left = 0, right = n;
        while (left < right) {
            int mid = (left + right) / 2;
            if (text.compare(sa[mid], m, pattern) < 0) left = mid + 1;
            else right = mid;
        }
        int start = left;
        
        right = n;
        while (left < right) {
            int mid = (left + right) / 2;
            if (text.compare(sa[mid], m, pattern) <= 0) left = mid + 1;
            else right = mid;
        }
        
        return right - start;
    }
    
    // 最长重复子串
    std::string longestRepeatedSubstring() {
        int maxLen = 0, maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (lcp[i] > maxLen) {
                maxLen = lcp[i];
                maxIdx = sa[i];
            }
        }
        return text.substr(maxIdx, maxLen);
    }
};

时间复杂度

操作 后缀树 后缀数组 说明
构建 O(n) O(n log n) 后缀树用 Ukkonen，后缀数组用倍增
子串查找 O(m) O(m log n) m 为模式长度
LCP 查询 O(1) O(log n) 需要 RMQ 预处理
最长重复子串 O(n) O(n)
空间 O(n) O(n)

后缀树 vs 后缀数组

特性 后缀树 后缀数组
构建复杂度 O(n) O(n log n)
空间 O(n) 指针开销大 O(n) 紧凑
实现复杂度 复杂 相对简单
实际应用 理论研究 广泛应用
子串查找 O(m) O(m log n)
选择建议：实际应用中优先选择后缀数组，空间紧凑、实现简单、常数因子小。后缀树适合理论研究或需要最优时间复杂度的场景。

应用场景

应用领域 具体问题
字符串匹配 多模式匹配、子串计数
重复结构 最长重复子串、重复子串计数
序列比对 最长公共子串、多个字符串公共子串
回文检测 最长回文子串
字符串压缩 LZ 因子分解
生物信息 DNA 序列分析、基因组比对

参考资料

  • Weiner, P. (1973). Linear Pattern Matching Algorithms
  • Kärkkäinen, J., Sanders, P. (2003). Simple Linear Work Suffix Array Construction
  • Kasai, T. et al. (2001). Linear-Time Longest-Common-Prefix Computation
  • 《算法导论》字符串匹配章节