C语言后缀树实现（从零构建高效字符串匹配结构）

为什么使用C语言实现后缀树？

C语言提供了对内存和指针的精细控制，非常适合实现底层数据结构。通过C语言字符串处理能力，我们可以高效构建和操作后缀树，为后续的高效字符串匹配打下基础。

基础结构定义

首先，我们需要定义后缀树的节点结构。每个节点包含子节点指针数组、起始和结束索引（用于表示边上的子串）、以及是否为叶节点的标记。

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_CHAR 256  // ASCII 字符集大小typedef struct SuffixTreeNode {    int start;                     // 边起始位置    int *end;                      // 边结束位置（使用指针以便所有叶节点共享）    struct SuffixTreeNode *children[MAX_CHAR];    struct SuffixTreeNode *suffixLink;  // 后缀链接    int index;                     // 叶节点存储后缀起始索引} Node;typedef struct SuffixTree {    char *text;    int textLen;    Node *root;    Node *activeNode;    int activeEdge;    int activeLength;    int remainingSuffixCount;    int *leafEnd;} SuffixTree;

Ukkonen 算法简介

构建后缀树最著名的算法是 Ukkonen 算法，它能在 O(n) 时间内构建后缀树（n 为字符串长度）。虽然完整实现较为复杂，但我们将采用简化版本，便于理解。

创建新节点

下面是一个创建新节点的辅助函数：

Node* createNode(int start, int *end) {    Node *node = (Node*)malloc(sizeof(Node));    node->start = start;    node->end = end;    node->suffixLink = NULL;    node->index = -1;    for (int i = 0; i < MAX_CHAR; i++) {        node->children[i] = NULL;    }    return node;}

构建后缀树（简化版）

为了教学目的，我们使用一个更直观但非线性时间的方法：逐个插入后缀。虽然效率不如 Ukkonen，但逻辑清晰，适合初学者。

void insertSuffix(Node *root, char *text, int suffixStart, int textLen) {    Node *current = root;    int i = suffixStart;    while (i < textLen) {        char ch = text[i];        if (current->children[ch] == NULL) {            // 创建新边            int *end = (int*)malloc(sizeof(int));            *end = textLen - 1;            current->children[ch] = createNode(i, end);            current->children[ch]->index = suffixStart;            break;        } else {            // 沿着现有边走            Node *child = current->children[ch];            int edgeLen = *(child->end) - child->start + 1;            int j;            for (j = 0; j < edgeLen && i + j < textLen; j++) {                if (text[child->start + j] != text[i + j]) break;            }            if (j == edgeLen) {                // 完全匹配，继续向下                i += edgeLen;                current = child;            } else {                // 需要分裂节点                int *oldEnd = child->end;                child->end = (int*)malloc(sizeof(int));                *(child->end) = child->start + j - 1;                // 创建新内部节点                Node *split = createNode(child->start, child->end);                split->children[text[child->start + j]] = child;                child->start += j;                // 创建新叶节点                int *newEnd = (int*)malloc(sizeof(int));                *newEnd = textLen - 1;                split->children[text[i + j]] = createNode(i + j, newEnd);                split->children[text[i + j]]->index = suffixStart;                // 更新父节点指针                current->children[ch] = split;                break;            }        }    }}SuffixTree* buildSuffixTree(char *text) {    int len = strlen(text);    SuffixTree *tree = (SuffixTree*)malloc(sizeof(SuffixTree));    tree->text = text;    tree->textLen = len;    tree->root = createNode(-1, NULL);    for (int i = 0; i < len; i++) {        insertSuffix(tree->root, text, i, len);    }    return tree;}

使用示例

下面是一个完整的使用示例，展示如何构建后缀树并打印所有后缀：

void printSuffixes(Node *node, char *text) {    if (node->index != -1) {        printf("Suffix: %s\n", text + node->index);        return;    }    for (int i = 0; i < MAX_CHAR; i++) {        if (node->children[i]) {            printSuffixes(node->children[i], text);        }    }}int main() {    char text[] = "banana$";    SuffixTree *tree = buildSuffixTree(text);    printf("All suffixes in the suffix tree:\n");    printSuffixes(tree->root, text);    return 0;}

总结

通过本教程，你已经掌握了如何用 C 语言实现一个基础的后缀树。虽然我们没有使用最优的 Ukkonen 算法，但这个简化版本能帮助你理解后缀树的核心思想。掌握后缀树算法不仅能提升你的数据结构能力，还能为解决复杂的高效字符串匹配问题提供强大工具。

如果你希望进一步优化性能，建议深入学习 Ukkonen 算法或 McCreight 算法。但在那之前，请确保你已完全理解本文所讲的基础概念和实现方式。

记住，无论是C语言后缀树实现还是其他高级数据结构，动手实践永远是最好的学习方式！