Trie树模板~~~
2024-08-27 06:50:31
const int maxnode = * + ;
const int sigma_size = ;
// 字母表为全体小写字母的Trie
struct Trie {
int ch[maxnode][sigma_size];
int val[maxnode];
int sz; // 结点总数
void clear() { sz = ; memset(ch[], , sizeof(ch[])); } // 初始时只有一个根结点
int idx(char c) { return c - 'a'; } // 字符c的编号 // 插入字符串s,附加信息为v。注意v必须非0,因为0代表“本结点不是单词结点”
void insert(const char *s, int v) {
int u = , n = strlen(s);
for(int i = ; i < n; i++) {
int c = idx(s[i]);
if(!ch[u][c]) { // 结点不存在
memset(ch[sz], , sizeof(ch[sz]));
val[sz] = ; // 中间结点的附加信息为0
ch[u][c] = sz++; // 新建结点
}
u = ch[u][c]; // 往下走
}
val[u] = v; // 字符串的最后一个字符的附加信息为v
} // 找字符串s的长度不超过len的前缀
void find_prefixes(const char *s, int len, vector<int>& ans) {
int u = ;
for(int i = ; i < len; i++) {
if(s[i] == '\0') break;
int c = idx(s[i]);
if(!ch[u][c]) break;
u = ch[u][c];
if(val[u] != ) ans.push_back(val[u]); // 找到一个前缀
}
}
};
最新文章
- jsp重定向和转发
- 函数randint的使用
- mysql远程连接问题
- vconfig使用帮助
- Emacs学习心得之 基础配置
- 基于Python实现对PDF文件的OCR识别
- Js字符串与十六进制的相互转换
- SQL中迁移sql用户及密码脚本
- B - 一行盒子
- javascript中对变量类型的推断
- javaee 规范技术
- tomcat基础应用
- 使用dns批量管理普通主机名相关问题
- Maven服务器搭建
- Node.js之eventproxy详解
- python中元组与数组的区别
- js Infinity 属性
- python自学第8天,变量,递归
- oracle12建立非C##用户并且导入数据
- pip常用记录
热门文章
- WPF一个简单的垂直菜单样式的实现
- 一步步学习ASP.NET MVC3 (12)——FileResult
- NSCharacterset
- Pair Project: Elevator Scheduler [电梯调度算法的实现和测试]:思考题——谢勤政11061197
- portal、portlet、portlet容器三个概念
- Altium Designer完美双屏显示方法演示
- RxJava开发精要6 – Observables组合
- Ember.js demo8
- 企业2.0杀出一号种子选手 “Linkwedo”横空出世
- LINUX中的虚拟文件系统结构