HUD 5687(字典树)

news/2024/10/30 11:27:02/

反思:之前在删除单词的时候,只是删除掉单词前缀以后的字符,而没有把整个单词都删除掉,导致WA了很多次。

高手请略过...

AC代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string.h>
using namespace std;struct Dic {Dic *nt[26];//指向下一个字符的指针int num;//重叠字符出现的个数Dic() {num = 1;//明显,初始化的时候,字符就为1个for (int i = 0; i < 26; i++)nt[i] = NULL;}
};void insert(Dic *root, char *str) {int len = strlen(str);int pos;Dic *p = root;for (int i = 0; i < len; i++) {pos = str[i] - 'a';if (p->nt[pos] == NULL) p->nt[pos] = new Dic;//字典中不存在这个字符,则插入一个新的结点else p->nt[pos]->num++;//如果该字符存在,则该结点的重叠个数+1p = p->nt[pos];}
}bool search(Dic *root, char *str) {int len = strlen(str);int pos;Dic *p = root;for (int i = 0; i < len; i++) {pos = str[i] - 'a';if (p->nt[pos] == NULL)return false;p = p->nt[pos];}return true;
}void Del(Dic *root, char *str) {Dic *pre = NULL, *p = root;int len = strlen(str);int pos, sum;//遍历到前缀的最后一个字符for (int i = 0; i < len; i++) {pos = str[i] - 'a';if (p->nt[pos] == NULL)return;p = p->nt[pos];}sum = p->num;//拥有这个前缀的单词的个数p = root;for (int i = 0; i < len; i++) {pos = str[i] - 'a';pre = p;//记录前一个结点,方便删除p = p->nt[pos];p->num -= sum; //因为要删除“拥有这个前缀单词”,所以就需要在树上减去 “拥有这个前缀的单词的个数”if (p->num == 0) //如果为0,则表明:拥有这个前缀的单词都不存在了,所以直接赋值为NULLpre->nt[pos] = NULL;}
}int main() {int N;Dic *root = new Dic;cin >> N;while (N--) {char order[10], str[31];scanf("%s %s", order, str);if (order[0]=='i') {insert(root, str);}else if (order[0] == 'd') {Del(root, str);}else if (order[0] == 's') {if (search(root, str)) printf("Yes\n");else printf("No\n");}}return 0;
}

 


http://www.ppmy.cn/news/209548.html

相关文章

(转载)基于鱼群算法的函数寻优算法(matlab实现)

1 理论基础 1.1 人工鱼群算法概述 人工鱼群算法是李晓磊等人于2002年提出的一类基于动物行为的群体智能优化算法。该算法是通过模拟鱼类的觅食、聚群、追尾、随机等行为在搜索域中进行寻优&#xff0c;是集群体智能思想的一个具体应用。生物的视觉是极其复杂的&#xff0c;它…

P5687 [CSP-SJX2019] 网格图(Kruskal扩展)

题目链接 Kruskal 思想的扩展&#xff0c;一开始想到了贪心取各行各列中的最小边权&#xff0c;但是没有把握好环的判断问题&#xff0c;只敲了个裸的 Kruskal 水了水&#xff0c;后面参考了洛谷第一篇的题解&#xff0c;其实就是简单地记录一下已经取的行/列的数目就行啦… #…

HDU5687 Problem C【字典树】

Problem C Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 2772 Accepted Submission(s): 768 Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; …

HDU 5687 Problem C 字典树

Problem C Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 2902 Accepted Submission(s): 793 Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; …

HDU 5687 Problem C

Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; 1、insert : 往神奇字典中插入一个单词 2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词 3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串 …

hdu 5687 裸字典树

度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; 1、insert : 往神奇字典中插入一个单词 2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词 3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串 Input 这里仅…

HDU 5687 字典树入门

Problem C Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 1423 Accepted Submission(s): 426 Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; 1、inse…

ibm 2011年服务器型号,IBM x 系列服务器CPU型号

94Y6685. 英特尔至强E5-2690 处理器&#xff0c;8核&#xff0c;主频 2.9GHZ,20MB 高速缓存&#xff0c;最大内存速度 1600MHZ,功率为 135w,带风扇 RMB30,631 69Y5331. 英特尔至强E5-2680 处理器&#xff0c;8核&#xff0c;主频 2.7GHZ,20MB 高速缓存&#xff0c;最大内存速度…