HDU 5687 Problem C ( 字典树前缀增删查 )
2024-10-07 11:11:26
题意 : 度熊手上有一本神奇的字典,你可以在它里面做如下三个操作:
1、insert : 往神奇字典中插入一个单词
2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词
3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串
分析 : 利用字典树,插入操作时对于每一个节点的标记权值+1,代表此前缀+1,然后删除操作的时候尤为要注意的就是对于给出的前缀,不能在字典树上将权值置为0,因为如果现在假设已经插入了 abc、ab 现在要求 delete abc 则不能将 ab 这个前缀的标记权值变成 0 ,这很显然是不对的( 虽然自己傻逼被坑了=_= ),正确的做法是找到 abc 在字典树出现的次数,然后再从 root 节点将 abc 这个前缀途经的节点减去这个次数,最后面对 abc 后面的节点 free 掉即可
#include<string.h> #include<stdio.h> #include<malloc.h> #include<iostream> #include<algorithm> using namespace std; ; struct Trie { Trie *Next[maxn]; int flag; inline void init(){ ; ; i<maxn; i++) this->Next[i] = NULL; } }; Trie *root = (Trie *)malloc(sizeof(Trie)); inline void DelTrie(Trie *T) { if(T == NULL) return ; ; i<maxn; i++){ if(T->Next[i] != NULL) DelTrie(T->Next[i]); } free(T); return ; } void CreateTrie(char *str, bool isDel) { int len = strlen(str); Trie *p = root, *tmp; ; ; i<len; i++){ int idx = str[i]-'a'; if(!isDel){ if(p->Next[idx] == NULL){ tmp = (Trie *)malloc(sizeof(Trie)); tmp->init(); p->Next[idx] = tmp; p = p->Next[idx]; }; p = p->Next[idx]; } }else{ if(p->Next[idx] != NULL){ DelNum = p->Next[idx]->flag; p = p->Next[idx]; }else return ; } } if(isDel){ p = root; ; i<len; i++){ int idx = str[i] - 'a'; if(p->Next[idx] == NULL) return ; ){ DelTrie(p->Next[idx]); p->Next[idx] = NULL; return ; } p->Next[idx]->flag -= DelNum; p = p->Next[idx]; } } } bool FindTrie(char *str) { int len = strlen(str); Trie *p = root; ; i<len; i++){ int idx = str[i]-'a'; ) p = p->Next[idx]; else return false; }return true; } int main(void) { root->init(); int n; scanf("%d", &n); ], str[]; while(n--){ scanf("%s", command); ){ scanf("%s", str); CreateTrie(str, false); } ){ scanf("%s", str); CreateTrie(str, true); } else{ scanf("%s", str); FindTrie(str)?puts("Yes"):puts("No"); } }DelTrie(root); ; }
瞎 : 要冷静分析啊!字典树上是怎么在跑的,还有内存问题啊!很裸的字典树写不出来就傻逼了!
最新文章
- 0032 Java学习笔记-类加载机制-初步
- VS工具--GhostDoc
- 非常有趣的Console
- Android Studio使用教程-菜单(Edit)
- Web 开发人员系统重装备忘录
- dbcp/c3p0连接池设置mysql会话变量
- Power Strings(poj 2406)
- PSP0表格二
- 安装成功的nginx如何添加未编译安装模块
- TCSRM 591 div2(1000)(dp)
- 【转】关于 Endnote 与 Word 卡死问题 标记语法错误
- PHP运行出现Notice : Use of undefined constant 的解决方法【已测】
- PHP之intval()
- 窗口嵌入到另一个窗口(VC和QT都有)
- hdu4352(数位dp)
- 配置RIPng(PT)
- vue2 设置网页title的问题
- EOS开发基础之六:使用cleos命令行客户端操作EOS——智能合约之eosio.msig和eosio.system
- JVM的内存区域划分(转)
- Android Studio 错误: 非法字符: &;#39;\ufeff&;#39; 解决方式|错误: 须要class, interface或enum