後綴樹（Suffix Tree）C++ 實現與應用詳解

後綴樹（Suffix Tree）C++ 實現與應用詳解

後綴樹是一種強大的字符串數據結構，能在線性時間內構建，並在線性時間內完成模式匹配、最長公共子串等複雜查詢。本文通過一個具體問題引入，給出基於 C++ STL 的完整實現代碼，並解析核心邏輯。

問題場景

給定一個長字符串 S 和多個短模式串集合 {T1, T2, ...}，要求高效查找每個 Ti 在 S 中所有出現的起始位置。暴力匹配在長文本多模式場景下效率極低，後綴樹可將查詢時間降至 O(|Ti|)。

核心代碼實現

/* 
 * Suffix Tree Implementation
 * Compiler: gcc 4.8.1 / Eclipse CDT
 */
#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;

class SuffixTreeNode {
    map<char, SuffixTreeNode*> children;
    char value;
    vector<int> indexes; // 存儲該節點對應後綴的起始索引
public:
    SuffixTreeNode() : value(0) {}
    
    // 遞歸插入後綴
    void insertString(const string& s, int index) {
        indexes.push_back(index);
        if (s.empty()) return;
        
        value = s[0];
        SuffixTreeNode* child = nullptr;
        auto it = children.find(value);
        if (it != children.end()) {
            child = it->second;
        } else {
            child = new SuffixTreeNode();
            children[value] = child;
        }
        child->insertString(s.substr(1), index);
    }
    
    // 查詢模式串對應的所有起始位置
    vector<int> getIndexes(const string& s) const {
        if (s.empty()) return indexes;
        char first = s[0];
        auto it = children.find(first);
        if (it != children.end()) {
            return it->second->getIndexes(s.substr(1));
        }
        return vector<int>(); // 未找到
    }
    
    ~SuffixTreeNode() {
        for (auto& p : children) delete p.second;
    }
};

class SuffixTree {
    SuffixTreeNode* root;
public:
    explicit SuffixTree(const string& s) : root(new SuffixTreeNode()) {
        for (int i = 0; i < (int)s.length(); ++i) {
            root->insertString(s.substr(i), i);
        }
    }
    
    vector<int> getIndexes(const string& s) const {
        return root->getIndexes(s);
    }
    
    ~SuffixTree() { delete root; }
};

int main() {
    string testString = "mississippi";
    string patterns[] = {"is", "sip", "hi", "sis"};
    SuffixTree tree(testString);
    
    for (const auto& pat : patterns) {
        vector<int> pos = tree.getIndexes(pat);
        if (!pos.empty()) {
            cout << pat << " ";
            for (int p : pos) cout << p << " ";
            cout << endl;
        }
    }
    return 0;
}

輸出結果

is 1 4 
sip 6 
sis 3 

關鍵點解析

1. 節點設計：使用 map<char, Node*> 存儲子節點，適用於字符集較大或動態場景；indexes 向量記錄該節點代表的所有後綴起始位置。
2. 構建過程：對長度為 n 的字符串，依次插入 n 個後綴（S[i..n-1]），每個後綴插入耗時 O(長度)，總構建時間 O(n²)。註：此為簡化版，Ukkonen 算法可達 O(n) 構建，但實現複雜度高得多。
3. 查詢過程：從根節點按模式串字符逐層遍歷，若中途斷開則不存在；到達末節點後，其 indexes 即為所有匹配位置，查詢時間 O(|pattern|)。
4. 內存管理：析構函數遞歸釋放所有子節點，防止內存洩漏。

應用場景與擴展

• 多模式串匹配（如病毒特徵庫掃描、敏感詞過濾）
• 最長公共子串、最長重複子串查找
• 字符串壓縮、生物信息學序列分析

對於超大規模文本（GB 級），需考慮後綴數組或壓縮後綴樹（如 Suffix Automaton）以節省內存。但對於中等長度文本及教學演示，本實現清晰易懂且功能完備。