查询前缀出现的次数----字典树
查询 出现 ---- 字典 次数 前缀
2023-09-14 08:56:55 时间
#include<iostream> #include<string.h> #include<algorithm> using namespace std; int trie[400001][26], len, root, tot, sum[400001];//sum是统计出现个数 bool p; int n, m; char s[11]; void insert() { len = strlen(s); root = 0; for (int i = 0; i<len; i++) { int id = s[i] - 'a'; if (!trie[root][id]) trie[root][id] = ++tot;//字母插入一个新的位置,存进数组里面,否则不做处理 sum[trie[root][id]]++;//前缀后移一个位置保存 ,就是把这个前缀出现的次数保存在这个前缀的后一个位置 root = trie[root][id]; } } int search() { root = 0; len = strlen(s); for (int i = 0; i<len; i++) { int id = s[i] - 'a'; if (!trie[root][id]) return 0; root = trie[root][id]; }//root经过此循环后变成前缀最后一个字母所在位置的后一个位置 return sum[root];//因为前缀后移了一个保存,所以此时的sum[root]就是要求的前缀出现的次数 } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> s; insert(); } int m; cin >> m; for (int i = 1; i <= m; i++) { cin >> s; cout << search(); //printf("%d\n", search()); } //system("pause"); return 0; }
相关文章
- mongodb联表查询_mongodb聚合查询
- Hsql 查询_sql数据查询
- 热门好用的手机号码归属地和运营商查询
- 查询SQL Server 交集查询实战演练(sqlserver交集)
- MySQL查询:查看数据表的总数(mysql查询表总数)
- 错误MySQL查询出现1064错误解决方法(mysql出现1064)
- MySQL索引如何提高LIKE查询效率(mysql索引like)
- SQL Server查询出现错错列,怎么解决?(sqlserver错列)
- 如何解决 Oracle 数据库中出现的乱码查询问题(oracle乱码查询)
- MSSQL查询第几条记录?(mssql 第几条)
- 如何查询Redis中热门Key(查询redis热键)
- 查看Redis是否出现死锁(查询redis是否死锁)
- 慢查询探究Redis慢查询的真相(为何会出现redis)
- 提高查询效率,MySQL读取不加锁(mysql 不加锁读取)
- Mysql中分页查询的两个解决方法比较
- 解析php根据ip查询所在地区(非常有用,赶集网就用到)