trie树的最基本题型,题目是要统计在一个字典中,有多少匹配指定前缀的单词,因为trie树是一棵前缀树,所以对于trie树的每个节点在插入时只要经过这个节点便对这个计数变量加一,最后按照trie查询进行统计;返回统计量即可。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct node
{
int num;
bool f;
int next[26];
void init(){num=0;f=0;memset(next,-1,sizeof(next));};
}trie[1000000];
int p;
char input[100];
void root()
{
trie[p=0].init();
}
void insert(char* a)
{
int index=0;
int len=strlen(a);
int cur;
for(int i=0;i<len;i++)
{
cur=a[i]-'a';
if(trie[index].next[cur]==-1)
{
trie[++p].init();
trie[index].next[cur]=p;
}
trie[index].num++;
index=trie[index].next[cur];
}
trie[index].f=1;
trie[index].num++;
}
int find(char* a)
{
int index=0;
int len=strlen(a);
int cur;
for(int i=0;i<len;i++)
{
cur=a[i]-'a';
if(trie[index].next[cur]==-1)return 0;
index=trie[index].next[cur];
}
return trie[index].num;
}
int main()
{
char input[100];
int word;
int query;
root();
int i;
while(1)
{
cin.getline(input,20);
//scanf("%s",input);
if(strlen(input)==0) break;
insert(input);
}
while(scanf("%s",input)!=EOF)
{
//scanf("%s",input);
cout<<find(input)<<endl;
}
return 0;
}
分享到:
相关推荐
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
算法-数塔(HDU-2084).rar
算术(HDU-6715).rar
算法-确定比赛名次(HDU-1285).rar
最短路(HDU-2544).rar
算法-命运(HDU-2571)(包含源程序).rar
算法-连连看(HDU-1175)(包含源程序).rar
算法-欧拉回路(HDU-1878)(包含源程序).rar
算法-排列组合(HDU-1521)(包含源程序).rar
算法-排列2(HDU-1716)(包含源程序).rar
算法-迷宫城堡(HDU-1269)(包含源程序).rar
算法-免费馅饼(HDU-1176)(包含源程序).rar