hdu1251 字典树

题干：
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

字典树模板，初始时是一棵空树，然后根据题干给出的数据开始建树，没节点就加节点。一层创建完后记得移动root节点，好进行下一层创建。

#include <bits/stdc++.h>
using namespace std;
int trie[400010][26],len,root,tot,sum[400010];
bool p;
char s[26];
void insert()
{
	len=strlen(s);
	root=0; 
	int i,j;
	for (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;
	int i,j;
	len=strlen(s); 
	for (i=0;i<len;i++)
	{
		int id=s[i]-‘a‘;
		if (!trie[root][id])
		return 0;//无此节点，返回0
		root=trie[root][id]; 
		//root经过此循环后变成前缀最后一个字母所在位置的后一个位置 
	}
	return sum[root]; 
}
int main()
{
	int i,j,f=0;
	while(gets(s))
	{
		if (strlen(s)==0)
		{
			f=1;
			continue;
		}
		if (!f)
		insert();
		else
		cout<<search()<<endl;
	}

	return 0;
}

hdu1251 字典树

原文：https://www.cnblogs.com/shidianshixuan/p/14427292.html