用C++设计一个可描述自动机数据结构的代码

以下是一个简单的自动机数据结构的 C++ 代码示例：

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

using namespace std;

// 定义自动机节点结构体
struct Node {
    unordered_map<char, Node*> next; // 节点的下一步状态，使用哈希表存储
    bool is_end = false; // 是否为字符串结束节点
};

// 自动机类
class Trie {
public:
    Trie() {
        root = new Node(); // 初始化根节点
    }

    ~Trie() {
        clear(root); // 释放内存
    }

    void insert(string word) {
        Node* p = root;
        for (char c : word) {
            if (!p->next.count(c)) { // 如果当前字符节点不存在
                p->next[c] = new Node(); // 新建一个节点
            }
            p = p->next[c]; // 移动到下一个节点
        }
        p->is_end = true; // 最后一个字符节点标记为字符串结束
    }

    bool search(string word) {
        Node* p = root;
        for (char c : word) {
            if (!p->next.count(c)) { // 如果当前字符节点不存在
                return false; // 字符串不存在
            }
            p = p->next[c]; // 移动到下一个节点
        }
        return p->is_end; // 返回最后一个字符节点是否为字符串结束节点
    }

    bool startsWith(string prefix) {
        Node* p = root;
        for (char c : prefix) {
            if (!p->next.count(c)) { // 如果当前字符节点不存在
                return false; // 前缀不存在
            }
            p = p->next[c]; // 移动到下一个节点
        }
        return true; // 返回前缀存在
    }

private:
    Node* root;

    void clear(Node* p) {
        if (p == nullptr) {
            return;
        }
        for (auto& [c, next_p] : p->next) { // C++17 的结构化绑定语法
            clear(next_p);
        }
        delete p;
    }
};

// 测试
int main() {
    Trie trie;
    trie.insert("hello");
    trie.insert("world");
    cout << trie.search("hello") << endl; // 输出 1
    cout << trie.search("hi") << endl; // 输出 0
    cout << trie.startsWith("hell") << endl; // 输出 1
    cout << trie.startsWith("wor") << endl; // 输出 1
    cout << trie.startsWith("abc") << endl; // 输出 0
    return 0;
}

这里使用了哈希表来存储自动机节点的下一步状态，插入、搜索和前缀匹配的时间复杂度均为 $O(m)$，其中 $m$ 为字符串长度。如果需要使用自动机进行字符串匹配等操作，还需要在节点中存储一些额外信息，例如 AC 自动机中的 fail 指针等。