`
breakallerror
  • 浏览: 7218 次
  • 性别: Icon_minigender_1
  • 来自: 合肥
最近访客 更多访客>>
社区版块
存档分类
最新评论

字典树

阅读更多

Let the Balloon Rise

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 30911    Accepted Submission(s): 10169


Problem Description
Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges' favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.

This year, they decide to leave this lovely job to you. 
 

Input
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) -- the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.

A test case with N = 0 terminates the input and this test case is not to be processed.
 

Output
For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.
 

Sample Input
5 green red blue red red 3 pink orange pink 0
 

Sample Output
red pink
 

Author
WU, Jiazhi
 

Source
 

Recommend
JGShining
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2011 HDU ACM Team. All Rights Reserved.
Designer & Developer Wang Rongtao LinLe GaoJie GanLu
Total 0.000377(s) query 1, Server time : 2011-08-03 14:51:21, Gzip enabled

 

 

这题是最基本的字典树,代码ac了。但是写的很乱

 

 

#include<iostream>
#include<string>
using namespace std;
int imax = 0 ;
char maxs[16];

struct word
{
       word*next[26];
       bool end ;
       int num ;
};

void creat(word* head , char w[])
{
     word*p = head ;
     for(int i =0 ; w[i] ; i++)
     {
             int n = w[i] - 'a';
             if(p->next[n] == NULL)
             {
                           p->next[n] = new word;
                           for(int i = 0; i < 26 ; i++)
                           {
                                   p->next[n]->next[i] = NULL;
                           }
                           p->next[n]->end = false ;
                           p->next[n]->num = 0 ;
             }
             
             p = p->next[n];     
     }
     p->num ++ ;
     p->end = true ;
}

void search(word *p , char w[] ,int L = -1 ,int num = -1)
{
     if(num != -1)
     {
         w[L] = char(num+'a');
         w[L+1] = 0 ;  
     }
     if(p->end)
     {
         if(p->num >imax)
         {
                   imax = p->num ;
                   strcpy(maxs,w);
         }
     }
     for(int i = 0 ; i<26 ; i++)
     {
             if(p->next[i]!= NULL)
             {
                             search(p->next[i] , w ,L+1 ,i);
             }
     }
}




int main()
{
    int n = 0 ;
    while(cin >>n)
    {
              if(n==0)
              break;
              imax = 0 ;
              word*head = new word;
              for(int i = 0 ; i < 26 ; i++)
              {
                      head->next[i] = NULL;
              }
              head ->num = 0 ;
              head ->end = false ; 
              
              char str[16];
              for(int j = 0 ; j < n ; j++)
              {
                      cin>>str ;
                      creat(head , str);
              }
              
              char maxstr[16];
              search(head , maxstr , -1 , -1);
              cout<<maxs<<endl;
    
    }
}
 
分享到:
评论

相关推荐

    快速单词拼写检错程序(字典树实现)

    快速单词拼写检错程序基于字典树的实现是一个高效的方法来检查文本中的拼写错误。这个Java程序利用了数据结构——字典树(Trie),也被称为前缀树或PAT树,它在处理字符串相关的搜索问题时表现出色。下面我们将深入...

    字典树~java语言

    在IT领域,字典树(Trie,也称为前缀树或字首树)是一种用于存储动态集合或关联数组的数据结构。它以高效的方式处理字符串查询,尤其适用于查找具有共同前缀的单词。字典树的主要优点是它可以快速地通过共享前缀来...

    acm 算法 字典树模板

    ACM 算法字典树模板 在算法竞赛中,字典树(Trie)是一种常用的数据结构,用于解决字符串匹配问题。下面是字典树的基本概念和实现细节。 字典树的基本概念 字典树是一种树形数据结构,用于存储字符串集合。它的每...

    字典树及其应用 功能介绍及实现

    "字典树及其应用" 字典树是一种树形结构,也称为单词查找树或Trie树。它是一种哈希树的变种,典型应用是用于统计、排序和保存大量的字符串(但不仅限于字符串)。字典树的优点是利用字符串的公共前缀来节约存储空间...

    字典树查找统计及单词

    在IT领域,字典树(Trie,也称为前缀树或字首树)是一种非常重要的数据结构,常用于高效地存储和检索字符串。在这个场景中,标题“字典树查找统计及单词”指的是利用字典树进行单词查找、统计以及可能的分析操作。...

    字典树算法 c语言实现

    字典树,也被称为Trie或前缀树,是一种用于高效存储和检索字符串的数据结构。在C语言中实现字典树,主要涉及到链表、指针操作和动态内存分配等核心概念。以下是对字典树算法及其C语言实现的详细说明: ### 1. 字典...

    字典树_英汉词典

    ### 字典树(Trie Tree)相关知识点 #### 一、什么是字典树? 字典树,也称为前缀树或Trie树,是一种用于存储字符串的高效数据结构。它利用了字符串之间的公共前缀来减少存储空间的需求,并且能够快速进行插入、...

    ACM Trie树 模板 字典树

    ACM Trie树 模板,字典树模板,数据结构

    字典树的模版(模版)

    ### 字典树模版详解 在计算机科学领域,字典树(Trie Tree),也被称为前缀树或关键字树,是一种用于存储字符串集合的高效数据结构。与传统的搜索树相比,字典树能够通过共享公共前缀来节省空间,特别适用于处理...

    字典树php实现

    `TrieTree` 类是字典树的核心类,负责构建整个字典树结构,并提供插入、搜索等基本操作。 - **属性** - `$root`: 字典树的根节点。 - **构造函数** - 初始化 `$root` 为一个新的 `TrieNode` 实例,设置其 `$flag...

    字典树_字典树_

    字典树,也被称为Trie或前缀树,是一种用于高效存储和检索字符串的数据结构。在计算机科学中,字典树常被用于实现自动补全、关键词搜索、IP路由等功能,因为它能快速查找以特定前缀开头的所有字符串。下面将详细介绍...

    字典树KMP优先队列

    在IT领域,字典树(Trie)是一种高效的数据结构,用于存储字符串集合。它能够快速地进行前缀查找、插入和删除操作。字典树的每个节点代表一个字符串的前缀,根节点代表空字符串,每个节点的子节点对应一个字符,节点...

    可变长数组和字典树

    在编程领域,可变长数组(也称为动态数组)和字典树(又称Trie树或前缀树)是两种非常重要的数据结构。它们在不同的场景下有着广泛的应用,尤其在处理大量数据时能展现出高效的性能。 首先,我们来详细讨论可变长...

    Java实现字典树TrieTree

    在计算机科学中,字典树(也称为前缀树或TrieTree)是一种高效的数据结构,主要用于存储字符串集合。它能够快速地进行关键词查找、插入和删除操作,尤其适合于处理大量的词汇数据,如在四六级英语考试的高频词汇查询...

    二十六叉字典树

    ### 二十六叉字典树知识点详解 #### 1. 二十六叉字典树简介 二十六叉字典树(Trie),也被称为前缀树或关键字树,是一种高效的数据结构,主要用于处理字符串集合。它能够有效地支持插入、删除、搜索等操作,并且...

    C语言字典树创建和搜索示例

    在计算机科学中,字典树(也称为Trie或前缀树)是一种高效的数据结构,尤其适用于快速查找和插入字符串。在C语言中实现字典树可以帮助我们构建一个高效的字符串处理程序,例如搜索引擎或者自动补全功能。在这个示例...

    输入法模拟程序(字典树词频统计)

    《输入法模拟程序:字典树与词频统计的智慧结晶》 在信息技术飞速发展的今天,输入法作为人机交互的重要桥梁,其智能化程度直接影响到用户的使用体验。本项目“输入法模拟程序”旨在利用数据结构和算法的力量,创建...

    字典树实例--java实现

    在IT领域,字典树(Trie,也称为前缀树或字典树)是一种用于存储动态集合或关联数组的数据结构。它允许我们快速查找、插入和删除字符串,特别是对于有公共前缀的字符串,效率非常高。这个实例是用Java语言实现的,...

    字典树的实现

    字典树的实现

    深度优先遍历字典树(统计单词出现的个数)

    在字典树(Trie,也称为前缀树或数字检索树)中应用深度优先遍历,可以有效地统计单词出现的个数。字典树是一种数据结构,常用于存储大量字符串,它允许我们快速查找以特定前缀开头的所有单词。 在Java中,实现字典...

Global site tag (gtag.js) - Google Analytics