HDU 1251：统计难题 ← 字典树（Trie树）

【算法分析】
字典树，又称Trie树、单词查找树，是用于字符串快速检索的多叉树。
其原理是利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

下文中的insert()、calPre()、query()、beginWith()函数，是字典树的经典函数。
在HDU 1251中，query()、beginWith()函数不需要，只是为了方便学习，将它们也写在代码里了。
另外，HDU 1251题目没有给出数据范围，但在调试代码时，发现数据范围至少要声明到10^6的范围才能通过。
特别需要说明的是，HDU不支持万能头文件。

【问题描述】
题目来源：Problem - HDU 1251
Ignatius最近遇到一个难题，老师交给他很多单词（只有小写字母组成，不会有重复的单词出现），现在老师要他统计出以某个字符串为前缀的单词数量（单词本身也是自己的前缀）。

【数据输入】
输入数据的第一部分是一张单词表，每行一个单词，单词的长度不超过10，它们代表的是老师交给Ignatius统计的单词，一个空行代表单词表的结束。
第二部分是一连串的提问，每行一个提问，每个提问都是一个字符串。
注意：本题只有一组测试数据，处理到文件结束。

【数据输出】
对于每个提问，给出以该字符串为前缀的单词的数量。

【输入输出样例】
输入样例：
banana
band
bee
absolute
acm

ba
b
band
abc

输出样例：
2
3
1
0

【算法代码】

#include 
#include 
using namespace std;

const int maxn=1e6+10;
int son[maxn][26];
int sum[maxn];
int over[maxn];
int tot;

void insert(string s) { //将字符串s插入字典树中
    int p=0;
    for(int i=0; i 


【参考文献】
 https://blog.csdn.net/qq_43663263/article/details/113422046
 https://blog.csdn.net/qq_38891827/article/details/80532462
 http://acm.hdu.edu.cn/showproblem.php?pid=1251
 https://blog.csdn.net/yu121380/article/details/81121943
 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5503835.html