卢俊达

题目大意：

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

思路：

字典树模板题。

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
struct trie
//利用结构体来封装字典树的节点。
{
	trie* next[26];
	int num;
	trie()
	//构造函数。
	{
		for(int i=0;i<26;i++)
			next[i]=NULL;
		num=0;
	}
}root;
void insert(char* s)
//将字符串s所表示的单词插入到字典树中。
{
	trie *p=&root;
	for(int i=0;s[i]!='\0';i++)
	{
		if(p->next[s[i]-'a']==NULL)
			p->next[s[i]-'a']=new trie;
		p=p->next[s[i]-'a'];
		p->num++;
	}
}
int find(char *s)
//返回值是以s为前缀的单词的数量。
{
	trie *p=&root;
	for(int i=0;s[i]!='\0';i++)
		if(p->next[s[i]-'a']==NULL)
			return 0;
		else
			p=p->next[s[i]-'a'];
	return p->num;
}
int main()
{
	char str[11];
	while(gets(str)&&str[0]!='\0')
		insert(str);
	while(~scanf("%s",str))
		printf("%d\n",find(str));
}