本文主要是介绍Trie数和AC自动机，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

字符串算法，随便学一下。

Trie树

字典树，用来求前缀的匹配。

比较简单，每一个字符都是一个节点，相同字符都是相同节点，然后就完了。

我们可以设这里插入的字符串分别是

abc
cab
bac
bca

这就是 Trie 构造出来的样子，是不是一下就懂了？我们查询的时候根据这个树跳就完了。
代码也很好实现，用一个结构体存，也可以用多个数组。

一个二位数组表示这个点的下一个点是什么，一维表示当前节点编号，另一维开好所有可能出现字符情况。

可能说的不是很清楚，举个例子，假设这个插入的字符串中只有 26 个英文字母，那我们就开 26 个数组，用这样提前开好的方式来存，同样的，如果有同时包含了大小写字母，那我们就可以开 52。

再来一个数组表示当前节点是否是一个单词结束的点。

这里直接给出代码：

给个模板题

constexpr int M = 65;
constexpr int N = 3E6 + 10;
struct node {
    int nxt[M];
} t[N];
int tag[N];

int trun(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';
    if (c >= 'A' && c <= 'Z') return c - 'A' + 26;
    return c - '0' + 52;
}

int idx = 0;
void insert(std::string s) {
    int n = s.size();
    int p = 0;
    for (int i = 0; i < n; i++) {
        // std::cout << p << "\n";
        int c = trun(s[i]);
        if (!t[p].nxt[c]) {
            t[p].nxt[c] = ++idx;
        }
        p = t[p].nxt[c];
        tag[p]++;
    }
}
int query(std::string s) {
    int n = s.size(), p = 0;
    for (int i = 0; i < n; i++) {
        int c = trun(s[i]);
        if (!t[p].nxt[c]) return 0;
        p = t[p].nxt[c];
    }
    return tag[p];
}

void solve() {
    int n, q;
    std::cin >> n >> q;
    
    for (int i = 0; i <= idx; i++) for (int j = 0; j < M; j++) t[i].nxt[j] = 0;
    for (int i = 0; i <= idx; i++) tag[i] = 0;
    idx = 0;

    for (int i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;
        insert(s);
    }
    while (q--) {
        std::string s;
        std::cin >> s;
        std::cout << query(s) << "\n";
    }
}

这篇关于Trie数和AC自动机的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！