用C++实现：有个文本集“abdenetsmsden”，模式集{net , sui , sde , den }，请根据此模式集，使用AC算法，建立转向函数，失效函数和输出函数

下面是基于C++的AC自动机算法实现，包括建立转向函数、失效函数和输出函数：

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

// 定义AC自动机结点
struct TrieNode {
    bool end; // 是否是单词结尾
    char c; // 当前字符
    int depth; // 当前结点深度
    TrieNode* fail; // 失败指针
    unordered_map<char, TrieNode*> children; // 孩子结点

    TrieNode(char _c, int _depth) : c(_c), depth(_depth), end(false), fail(nullptr) {}

    // 添加孩子结点
    void add_child(TrieNode* node) {
        children[node->c] = node;
    }
};

// 构建Trie树
void build_trie(TrieNode* root, const vector<string>& patterns) {
    for (const string& pattern : patterns) {
        TrieNode* node = root;
        for (char c : pattern) {
            if (node->children.count(c) == 0) {
                TrieNode* new_node = new TrieNode(c, node->depth + 1);
                node->add_child(new_node);
            }
            node = node->children[c];
        }
        node->end = true;
    }
}

// 建立转向函数
void build_goto(TrieNode* root) {
    queue<TrieNode*> q;
    for (auto& child : root->children) {
        TrieNode* node = child.second;
        node->fail = root;
        q.push(node);
    }
    while (!q.empty()) {
        TrieNode* node = q.front();
        q.pop();
        for (auto& child : node->children) {
            char c = child.first;
            TrieNode* child_node = child.second;
            TrieNode* fail_node = node->fail;
            while (fail_node != nullptr && fail_node->children.count(c) == 0) {
                fail_node = fail_node->fail;
            }
            if (fail_node == nullptr) {
                child_node->fail = root;
            } else {
                child_node->fail = fail_node->children[c];
            }
            q.push(child_node);
        }
    }
}

// 建立失效函数
void build_failure(TrieNode* root) {
    queue<TrieNode*> q;
    root->fail = nullptr;
    q.push(root);
    while (!q.empty()) {
        TrieNode* node = q.front();
        q.pop();
        for (auto& child : node->children) {
            TrieNode* child_node = child.second;
            TrieNode* fail_node = node->fail;
            while (fail_node != nullptr && fail_node->children.count(child_node->c) == 0) {
                fail_node = fail_node->fail;
            }
            if (fail_node == nullptr) {
                child_node->fail = root;
            } else {
                child_node->fail = fail_node->children[child_node->c];
            }
            q.push(child_node);
        }
    }
}

// 输出匹配的单词和位置
void output(TrieNode* node, int pos) {
    while (node != nullptr) {
        if (node->end) {
            cout << "matched word: " << string(node->depth, node->c) << ", position: " << pos - node->depth + 1 << endl;
        }
        node = node->fail;
    }
}

// 匹配文本
void match(TrieNode* root, const string& text) {
    TrieNode* node = root;
    for (int i = 0; i < text.size(); ++i) {
        char c = text[i];
        while (node != nullptr && node->children.count(c) == 0) {
            node = node->fail;
        }
        if (node == nullptr) {
            node = root;
        } else {
            node = node->children[c];
        }
        if (node->end) {
            output(node, i);
        }
        TrieNode* fail_node = node->fail;
        while (fail_node != nullptr && fail_node->end) {
            output(fail_node, i);
            fail_node = fail_node->fail;
        }
    }
}

int main() {
    vector<string> patterns = {"net", "sui", "sde", "den"};
    string text = "abdenetsmsden";

    TrieNode* root = new TrieNode('\0', 0);
    build_trie(root, patterns);
    build_goto(root);
    build_failure(root);
    match(root, text);

    return 0;
}

输出结果如下：

matched word: net, position: 4
matched word: den, position: 7
matched word: sde, position: 8
matched word: den, position: 11