HDU1251 统计难题[map的应用][Trie树]

一、题意

给出一组单词，另给出一组单词用作查询，求解对于每个用于查询的单词，前一组中有多少个单词以其为前缀。

二、分析

根据题目很容易想到hash的方法，首先可以朴素的考虑将第一组中的所有单词的前缀利用map进行统计，查询时直接得到结果

所以很容易可以得到以下代码。

注意：输入时的空行代表第一行的结束，利用gets读入并根据字符串的长度是否为0来判断；

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <map>

 using namespace std;

 const int maxn = ;

 char word[maxn];

 map<string,int> M;

 int main()

 {

     while(gets(word))

     {

         if(strlen(word) == )

             break;

         int L = strlen(word);

         for(int i=L;i>;i--)

         {

             word[i] = '\0';

             M[word]++;

         }

     }

     while(gets(word))

         printf("%d\n",M[word]);

     return ;

 }

然而，有些题目会卡map的用法，需要找到更高效的算法，这里可以使用Trie树，也就是前缀树、字典树来解决问题。

字典树的根节点为空，用边来表示字母，用根节点到某个节点的路径表示一个单词，字典树可以用数组表示，其中Tree[root][i]=k表示树上位置标号为root的节点的第i个子节点的位置编号为k

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 using namespace std;

 const int maxn = 2e6+;

 int Tree[maxn][],sum[maxn];

 int cnt;

 void Insert(char word[])

 {

     int L = strlen(word);

     int root = ;

     for(int i=;i<L;i++)

     {

         int id = word[i] - 'a';

         if(!Tree[root][id])

             Tree[root][id] = ++cnt;

         sum[Tree[root][id]]++;

         root = Tree[root][id];

     }

 }

 int Find(char word[])

 {

     int L = strlen(word);

     int root = ;

     for(int i=;i<L;i++)

     {

         int id = word[i] - 'a';

         if(!Tree[root][id])

             return ;

         root = Tree[root][id];

     }

     return sum[root];

 }

 int main()

 {

     char word[];

     cnt = ;

     while(gets(word))

     {

         if(strlen(word) == )

             break;

         Insert(word);

     }

     while(scanf("%s",word)!=EOF)

         printf("%d\n",Find(word));

     return ;

 }

注意，如果第二组单词用scan读入记得写!=EOF的形式

Map

HDU1251 统计难题[map的应用][Trie树]