`
jaychang
  • 浏览: 734646 次
  • 性别: Icon_minigender_1
  • 来自: 嘉兴
社区版块
存档分类
最新评论

Trie树 应用 Phone List

 
阅读更多

Phone List

时间限制:5000 ms  |  内存限制:65536 KB
描述

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another.

 

Let’s say the phone catalogue listed these numbers:

 

  • Emergency 911
  • Alice 97 625 999
  • Bob 91 12 54 26

In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.

输入

The first line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n , the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000.

 

Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

输出

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

样例输入
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
样例输出
NO
YES
     这题是一个标准的Trie树,如果处理好的话用排序也可以过,话说效率 还是挺不错的,但这里要讲的是Tire树做法。字符串处理的算法有很多,Trie树和Trie图(也就是AC自动机)都是很高效的数据结构,后缀数组也 是,但是由于后缀数组较为复杂,实现起来也比较恼火。Trie树是一棵度 m ≥ 2 的树,它的每一层分支不是靠整个关键码的值来确定,而是由关键码的一个分量来确定。关键码可以是英文字母,也可以是数字(这里的数据我们当作字符处理)。 Trie的基本操作有插入,删除,查询,实现起来也是比较容易的。
     用动态添加节点北航的OJ能过,但是POJ过不了,听说用静态的,本人暂时不会哈。所以给出的是动态添加的方法。

     针对这一题来分析:

           题 意:给n个串,看是否有一个串是另一个串的前缀。因为数据量相对来讲比较大,如果用两两比较,会TL,所以 O(n^2)显然过不了这题。  字典树却很容易处理,设置节点信息包括flag标志是否到达一个单词尾部,另外设置一个数组记录此结点的儿子结点的数组下标。在插入过程中就可以进行查询。

 

   自己写的Trie动态插入版本

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX 10

typedef struct TrieNode{
	bool isPhone;
	TrieNode *next[MAX];
	void initialTrie(){
		isPhone = false;
		for(int i = 0 ; i < MAX ; i++){
			next[i] = NULL;
		}
	}
}TrieNode;

bool isPrefixPhone = false;



void addWord(TrieNode *node,char *ch){
	if(node == NULL || *ch == '\0')
		return;
	TrieNode *p = node;
	int i,len;
	for(i = 0 ; i < (len=strlen(ch)) ; i ++){
		if(p->next[ch[i]-'0'] == NULL){
			TrieNode *tmp = (TrieNode*)malloc(sizeof(TrieNode));
			//初始化以temp为顶点节点的子树
			tmp->initialTrie();
			p->next[ch[i]-'0'] = tmp;	
		}else{		
			if(p->next[ch[i]-'0']->isPhone && i <= len - 1){
				isPrefixPhone = true;
				return;
			}
		}
		p = p->next[ch[i]-'0'];
	}
	p->isPhone = true;
	//如果先输入12,再输入1,那么就需要下面的代码进行判断
	for(i = 0 ; i < MAX ; i ++){
		if(p->next[i] != NULL){
			isPrefixPhone = true;
			return;
		}
	}
}


void delTree(TrieNode *root){
	for(int i = 0 ; i < MAX ; i ++){
		if(root->next[i] != NULL){
			delTree(root->next[i]);
		}
		delete root->next[i];
	}
}



int main(){
	int t,n,i;
	char s[11];
	scanf("%d",&t);
	TrieNode *root = (TrieNode*)malloc(sizeof(TrieNode));
	while(t--){	
		root->initialTrie();
		isPrefixPhone = false;
		scanf("%d",&n);
		for(i = 0 ; i < n ; i ++){
			scanf("%s",s);
			if(isPrefixPhone) continue;
			addWord(root,s);
		}
		printf(isPrefixPhone ? "NO\n":"YES\n");
		delTree(root);
	}
	return 0;
}

 

    网上大牛写的静态版

 

 

    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int MAXNODE=500000;
    const int BRANCH=10;

    int Tree[MAXNODE][BRANCH],SIZE;
    bool Key[MAXNODE];
    bool Insert(char *str) {
        int Node=0;bool tof=false;
        for (int i=0;str[i];i++){
            int c=str[i]-'0';
            if(Tree[Node][c]==-1){
                Tree[Node][c]=++SIZE;tof=true;
                memset(Tree[SIZE],-1,sizeof(Tree[SIZE]));
            }
            if(Key[Node]) return false;
            Node=Tree[Node][c];
        }
        Key[Node]=true;
        return tof;
    }

    void Trie(){
        memset(Tree[0],-1,sizeof(Tree[0]));
        SIZE=0;
    }

    char str[15];
    int main()
    {
        int t,n;bool tof;
        scanf("%d",&t);
        while(t--){
            memset(Key,false,sizeof(Key));
            Trie();tof=true;
            scanf("%d",&n);
            for(int i=0;i<n;i++){
                scanf("%s",str);
                if(tof){
                    tof=Insert(str);
                }
            }
            if(tof) puts("YES");
            else puts("NO");
        }
    }
 

分享到:
评论

相关推荐

    IT笔试面试--Trie树前缀树常考题目及解析

    Trie树,又称字典树或前缀树,是一种用于快速检索的多叉树结构,广泛应用于字符串处理领域。它能有效地利用字符串的公共前缀来减少存储空间,并在查询、插入和删除等方面具有较高的效率。 #### Trie树基本特性 - *...

    Trie树入门,很容易上手

    Trie树的优点是可以快速地查找和插入字符串,但是缺点是内存消耗非常大,因此在实际应用中需要合理地使用Trie树。 在ACM/ICPC比赛中,Trie树是一种非常常用的数据结构,特别是在字符串处理和模式匹配方面。因此,...

    Trie 树实现的源码

    Trie树在很多应用中都有广泛的应用,如拼写检查、自动补全功能等。 #### 二、Trie树的基本结构 Trie树的每个节点通常包含一个指针数组和一个标志位。指针数组中的每个元素指向一个子节点,而标志位用来表示当前节点...

    用Trie树实现词频统计和单词查询

    一个简单的C语言程序:用Trie树实现词频统计和单词查询

    Python实现Trie树

    用Python实现Trie树的应用,并可以对英汉词典进行导入和检索、添加和删除,最终可以将导入的英汉词典保存到本地磁盘。内附两个.py文件,分别是tree.py和d_gui.py,tree.py是类和方法,d_gui.py是图形界面;一个.txt...

    基于Trie树模仿谷歌百度搜索框提示

    这个项目“基于Trie树模仿谷歌百度搜索框提示”旨在实现类似谷歌和百度搜索引擎的自动补全功能。我们将深入探讨Trie树数据结构以及如何使用Java来构建这样的系统。 首先,我们要理解什么是Trie树,也被称为前缀树或...

    trie树的实现(C)

    trie.c中定义了trie树的操作函数; trie.h为相应的头文件; test.c用于测试相关的函数。 在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,...

    从trie树谈到后缀树

    在实际应用中,Trie树特别适合处理大量字符串的集合,比如搜索引擎的关键词统计、文本词频分析等。例如,给定100000个长度不超过10的单词,如果使用Trie树,可以快速判断一个单词是否存在于集合中,并找到其首次出现...

    C++/C Trie树算法

    用C实现的数据结构Trie树算法 实验的函数的trie树的插入 搜索和删除

    双数组Trie树算法优化及其应用研究.pdf

    ### 双数组Trie树算法优化及其应用研究 #### 摘要与关键词解析 本文主要探讨了一种针对双数组Trie树(Double-Array Trie)算法的优化策略,并通过实验验证了该策略的有效性。双数组Trie树是一种高效的数据结构,常...

    Acm Trie树

    #### 三、Trie树的应用实例 假设我们需要构建一个Trie树,以存储字符串"abc"、"ab"、"bd"、"dda"。构建过程如下: 1. **创建根节点**:首先创建一个根节点,该节点没有任何信息。 2. **插入字符串**:对于每个字符...

    Trie树(字典数\字符树)基本原理

    Trie 树的主要应用场景包括: 1. 字符串查询:Trie 树可以高效地查询字符串是否存在于树中,并返回其出现的位置。 2. 字符串排序:Trie 树可以快速地对字符串进行排序,并且可以对长字符串进行处理。 3. 字符串插入...

    HASH(Trie)-.rar_HashTree.h_TRIE_hash树_trie树_字典树

    **哈希 Trie 树(HashTrie)与字典树(Trie树)详解** 哈希 Trie 树,也称为 HashTrie 或者是哈希化的 Trie 树,是一种结合了哈希表和 Trie 数据结构特点的数据结构。它在 Trie 树的基础上引入了哈希函数,提高了...

    Trie树题解1

    【Trie树题解1】 Trie树,又称字典树或前缀树,是一种用于高效存储和检索字符串的数据结构。它的主要特点是能够快速查找一个字符串是否是另...在实际编程竞赛或实际开发中,掌握Trie树的原理和应用是非常重要的技能。

    基于双数组Trie_树中文分词研究

    ### 基于双数组Trie树中文分词研究 #### 概述 本文献针对中文信息处理中的分词问题,研究了一种基于双数组Trie树(Double-Array Trie, DAT)的优化方法。传统的分词算法面临着空间利用率低、插入速度慢等问题,...

    NYOJ.290.DictionaryTree.zip_trie树c_字典树_高级数据结构

    Trie树的高级应用还包括压缩Trie树(Patricia Trie)和Trie树的变种,如Aho-Corasick算法,它在Trie树的基础上添加了“失败指针”以实现同时匹配多个模式的功能。在实际编程中,理解和掌握Trie树可以帮助我们更高效...

    trie树所有代码,试题打包

    这个压缩包包含的“王赟.doc”和“王赟.ppt”很可能是关于Trie树的详细讲解和实践题目,可能涵盖了Trie树的基本概念、实现原理、应用场景以及相关的编程练习。 首先,我们要理解Trie树的基本概念。Trie树是一种有序...

    DoubleArrayTrie(双数组Trie树)

    **DoubleArrayTrie(双数组Trie树)详解** DoubleArrayTrie(简称DAT),是一种高效的数据结构,常用于字符串的查找和匹配,特别是在分词检索、数据挖掘以及搜索引擎等领域有着广泛的应用。它是由日本学者高津陵...

    Trie树 结构描述 实现方法 用法

    在实际应用中,Trie树可以进行优化,如使用Trie压缩技术,减少空节点的存在,或者采用Patricia Trie(前缀共享树),减少存储空间。Trie树的变种还包括Aho-Corasick算法,用于一次性查找多个模式字符串。 总结来说...

    双数组Trie优化算法及其应用研究

    本文主要探讨了双数组Trie树(Double-Array Trie)算法的一种优化方法,并详细分析了其在实际应用中的表现,特别是在词典管理和自动分词领域。双数组Trie树作为一种高效的字符串搜索算法,在诸多场景下具有重要的应用...

Global site tag (gtag.js) - Google Analytics