Luogu P2922 [USACO08DEC]秘密消息Secret Message 字典树 Trie树

绝地灬酷狼 2022-01-09 10:49 170阅读 0赞

#### 本来想找\\(01Trie\\)的结果找到了一堆字典树水题。。。算了算了当水个提交量好了。 ####

#### 直接插入模式串，维护一个\\(Trie\\)树的子树\\(sum\\)大小，求解每一个文本串匹配时走过的链上匹配数和终点处的子树大小之和。 ####

#include <bits/stdc++.h> using namespace std; int top, sta[10010]; int n, m, l, s[10010], max_size; int ch[500010][2], sz[500010], sum[500010]; void push_up (int p) { sz[p] = sum[p]; if (ch[p][0]) sz[p] += sz[ch[p][0]]; if (ch[p][1]) sz[p] += sz[ch[p][1]]; } void add_str () { int now = 0; sta[top = 1] = 0; for (int i = 1; i <= l; ++i) { if (!ch[now][s[i]]) { ch[now][s[i]] = ++max_size; } // printf ("ch[%d][%d] = %d\n", now, s[i], ch[now][s[i]]); now = ch[now][s[i]]; sta[++top] = now; } sz[now]++; sum[now]++; while (top > 0) push_up (sta[top--]); } int get_str () { int now = 0, ans = 0; for (int i = 1; i <= l; ++i) { if (!ch[now][s[i]]) { return ans; } // printf ("now = %d, sum[now] = %d sz[now] = %d\n", now, sum[now], sz[now]); now = ch[now][s[i]]; ans += sum[now]; } // printf ("now = %d\n", now); ans += sz[now] - sum[now]; return ans; } int main () { cin >> m >> n; for (int i = 1; i <= m; ++i) { scanf ("%d", &l); for (int j = 1; j <= l; ++j) { scanf ("%d", &s[j]); } add_str (); } for (int i = 1; i <= n; ++i) { scanf ("%d", &l); for (int j = 1; j <= l; ++j) { scanf ("%d", &s[j]); } cout << get_str () << endl; } }

转载于:https://www.cnblogs.com/maomao9173/p/10441309.html

发表评论取消回复

表情：

评论列表（有 0 条评论，170人围观）

还没有评论，来说两句吧...

相关阅读

相关 Trie ——前缀树、字典树

说在前面： > `Map`映射数据结构和`Trie`的异同： > 相同：都能够根据`key`进行映射得到对应的值。 > 不同： > ① `Trie`中查询/添

逃离我推掉我的手/ 2023年07月10日 13:00/ 0 赞/ 24 阅读

相关 trie字典树实现

实现了一个简单的字典树. 假设所有的字符只有26个小写字母，并且除了节点出现的次数之外还增加了类似map功能的索引。假如不只有26个字母，需要相应的做一些修改。

一时失言乱红尘/ 2022年09月27日 15:22/ 0 赞/ 200 阅读

相关 646-Trie字典树

Trie字典树理论 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA

约定不等于承诺〃/ 2022年09月12日 13:43/ 0 赞/ 180 阅读

相关 Trie树（字典树）

很有段时间没写此系列了，今天我们来说Trie树，Trie树的名字有很多，比如字典树，前缀树等等。一：概念下面我们有and,as,at,cn,com这些关键词，那么如何

阳光穿透心脏的1/2处/ 2022年08月14日 00:00/ 0 赞/ 277 阅读

相关 Trie树——字典树

1、概述 Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。 Trie一词来自r

朴灿烈づ我的快乐病毒、/ 2022年05月21日 06:20/ 0 赞/ 326 阅读

相关 Trie树（字典树）

1. Trie树 Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索

梦里梦外;/ 2022年05月17日 05:21/ 0 赞/ 255 阅读

相关【树结构】Trie字典树

字典树概念使用场景：实现 1. 数据模型 2. 添加字符串 3. 删除操作 4. 获取单词频

曾经终败给现在/ 2022年02月28日 13:56/ 0 赞/ 278 阅读

相关 Luogu P2922 [USACO08DEC]秘密消息Secret Message 字典树 Trie树

本来想找\\(01Trie\\)的结果找到了一堆字典树水题。。。算了算了当水个提交量好了。直接插入模式串，维护一个\\(Trie\\)树的子树\\(sum\\)大小，

绝地灬酷狼/ 2022年01月09日 10:49/ 0 赞/ 171 阅读

相关 Luogu2922 [USACO08DEC]秘密消息Secret Message （Trie树）

统计以节点\\(i\\)结尾的数量与经过的数量 include <iostream> include <cstdio> include <cstring> inclu

布满荆棘的人生/ 2021年11月17日 05:12/ 0 赞/ 179 阅读

相关字典树trie

字典树　　又称单词查找树，[Trie树][Trie]，是一种[树形结构][Link 1]，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符

小灰灰/ 2021年09月30日 10:06/ 0 赞/ 441 阅读