hdu-1251 统计难题---字典树-白红宇

hdu-1251 统计难题---字典树

阅读量：6429 次

发布时间：2019-06-23

本文共 1269 字，大约阅读时间需要 4 分钟。

题目链接：

题目大意：

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

解题思路：

将每个单词存入字典树中，直接查询前缀出现次数即可，在加入字典树的时候，在每个字母表示的边上后面的节点数加1，记录前缀出现次数。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
           6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 #define lowbot(i) (i&(-i))12 using namespace std;13 14 const int maxn = 1e6 + 10;15 int tree[maxn][26];16 //字典树tree[u][v]表示编号为u的节点的下一个字母为v连接的节点的编号17 int idx(char c){ return c - 'a'; }//可以写成宏定义18 int tot = 1;//根节点编号为119 int sum[maxn];//标记以该节点结束的前缀出现次数20 void Insert(char s[], int u)//u表示根节点21 //插入字符串s22 {23 for(int i = 0; s[i]; i++)24 {25 int c = idx(s[i]);26 if(!tree[u][c])27 tree[u][c] = ++tot;28 sum[tree[u][c]]++; //前缀后面的那个节点数目加一29 u = tree[u][c];30 }31 }32 33 int Find_sum(char s[], int u)34 {35 for(int i = 0; s[i]; i++)36 {37 int c = idx(s[i]);38 if(!tree[u][c])return 0;39 u = tree[u][c];40 }41 return sum[u];//返回最后一个字母表示的边连接的后面那个节点，所记录的sum值42 }43 int main()44 {45 char s[15];46 while(gets(s) && strlen(s))Insert(s, 1);47 while(scanf("%s", s) != EOF)48 {49 printf("%d\n", Find_sum(s, 1));50 }51 return 0;52 }

转载于:https://www.cnblogs.com/fzl194/p/8951083.html

你可能感兴趣的文章