随手练——HDU 1251 统计难题
2024-10-20 17:36:18
知识点:前缀树。典型的前缀树模板。
这是用next[26]数组的版本,超内存了。(后来发现,用C++交不会超,G++就会超)
#include <iostream> #include <malloc.h> #include <string> using namespace std; typedef struct node{ int pass; ]; } *trieTree; trieTree init() { trieTree t = (trieTree)malloc(sizeof(node)); ; i < ; i++)t->next[i] = NULL; t->pass = ; return t; } void insert(trieTree T,string s) { node *n = T; ; i < s.length(); i++) { int index = s[i] - 'a'; if (T->next[index] == NULL) { node *t = init(); T->next[index] = t; } T = T->next[index]; T->pass++; } } int find(trieTree T, string s) { node *n = T; ; i < s.length(); i++) { int index = s[i] - 'a'; if (T->next[index] == NULL) { return NULL; } T = T->next[index]; } return T->pass; } int main() { trieTree T = init(); string s; while (getline(cin,s)) { if (s.empty()) break; insert(T, s); } while (getline(cin,s)) { cout << find(T, s) << endl; } ; }
一开始过不了,我还想了半天,网上别人代码,也是next[26]的写法都能AC,我咋过不了???人丑就不给过???这个难受啊。
其实,next指针数组,浪费了很多空间,用STL map重新改了一下(malloc只分配内存,我改成了new),内存大约节省了25%~30(自己实现一个简单键值对,节省的空间会更多),C++、G++编译器都能AC了。
#include <iostream> #include <map> #include <string> using namespace std; typedef struct node{ int pass; map<char,struct node *>m; } *trieTree; trieTree init() { trieTree t = new node; t->pass = ; return t; } void insert(trieTree T,string s) { ; i < s.length(); i++) { if (T->m.find(s[i]) == T->m.end()) { node *t = init(); T->m.insert(make_pair(s[i], t)); } T = T->m[s[i]]; T->pass++; } } int find(trieTree T, string s) { node *n = T; ; i < s.length(); i++) { if (T->m.find(s[i]) == T->m.end()) { return NULL; } T = T->m[s[i]]; } return T->pass; } int main() { trieTree T = init(); string s; while (getline(cin,s)) { if (s.empty()) break; insert(T, s); } while (getline(cin,s)) { cout << find(T, s) << endl; } ; }
最新文章
- Mysql 查看、创建、更改 数据库和表
- SQL周、日、月、年数据统计
- Log4J详解
- 获取客户端真实ip
- SQL时间戳的使用
- 2007Hanoi双塔问题
- 获取hadoop的源码和通过eclipse关联hadoop的源码
- linux 第一次获得root权限
- UIApplication对象及其代理UIApplicationDelegate[转]
- 理解 B*tree index内部结构
- 对武汉-and-IT软件开发的看法
- MFC简单绘制安卓机器人
- 理解梯度下降法(Gradient Decent)
- CSS3_文本样式
- HQL包含中文查询失败
- win10关不了机解决办法以及win10怎么禁止开机启动项
- 【css】3d导航效果
- 【Sichuan 2017D】Dynamic Graph
- mybatis resultType resultMap 区别
- 开发中经常遇到SVN清理失败的问题: