- 浏览: 717690 次
- 性别:
- 来自: 嘉兴
文章分类
- 全部博客 (386)
- Struts1.1 (2)
- Database (18)
- Core Java (15)
- Log4j (4)
- SSH (0)
- Dao (1)
- Architecture Design (1)
- References (2)
- Eclipse&MyEclipse (10)
- Hibernate (7)
- Spring (8)
- JavaMail (1)
- Data Structure And Algorithm (48)
- Struts 2 (2)
- SSI (1)
- SSL (2)
- JSTL (1)
- EJB3 (2)
- NET (2)
- XML (2)
- Components (2)
- Ant (3)
- Multi Thread (1)
- Performance Monitoring (1)
- Web Server (17)
- Oracle (1)
- jQuery (8)
- Regular Expression (1)
- Weblogic (1)
- Exception (1)
- Security (2)
- File Manipulation (1)
- JavaScript (12)
- JVM (2)
- HTML&DIV&CSS (4)
- Android (10)
- Beyond GFW (0)
- Business (0)
- SVN (6)
- 虚拟主机 (1)
- Virtual Host (3)
- My mentality (5)
- OS (15)
- ISPMP (3)
- Magento (5)
- Jsoup&HttpClient (7)
- LINUX (9)
- Database Design (0)
- Power Designer (1)
- TaobaoOpenPlatform (2)
- C/C++ (3)
- Maven (11)
- Quartz (1)
- Load Balance (1)
- Zabbix (4)
- Product&Business (1)
- Pay Interface (1)
- Tomcat (2)
- Redis (1)
- 集群 (1)
- Session (1)
- 共享Session (1)
- Jedis (1)
- jenkins (1)
- 持续集成 (1)
- Web前端 (1)
最新评论
-
aqq331325797:
特意注册账号上来说一句。牛逼!
swagger2.2.2 与 spring cloud feign冲突 -
KitGavinx:
跨顶级域名怎么保持sessionid一致?
Tomcat7集群共享Session 基于redis进行统一管理 -
jaychang:
dujianqiao 写道HI ,能否给一个完整的demo 啊 ...
淘宝订单同步方案 - 丢单终结者 -
GGGGeek:
找了一会儿,感觉mybatis应该没有这种操作,直到发现博主的 ...
mybatis collection list string -
dujianqiao:
HI ,能否给一个完整的demo 啊 ?
淘宝订单同步方案 - 丢单终结者
Phone List
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
针对这一题来分析:
题 意:给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"); } }
发表评论
-
【排序算法系列】希尔排序
2015-12-05 16:14 805希尔排序的概述: a[0]...a[n-1 ... -
归并排序
2015-06-20 15:28 859public class MergeSort { pub ... -
插入排序
2015-06-20 15:27 458/** * 插入排序1 容易理解 * * ... -
有序线性链表归并
2013-10-05 11:30 1511#include<stdio.h> #incl ... -
Trie树 单词查找树 键树(JAVA版附分析说明)
2012-06-13 10:27 5117来源于英文“retrieval”. ... -
Trie树 单词查找树 键树
2012-06-12 08:59 1117转自:http://zh.wik ... -
数字金额转中文大写金额
2010-11-26 15:09 1401/** * 用来将数字金额转化成中文大写的金额 ... -
汉诺塔递归算法
2010-11-25 08:17 1319import java.util.Scanner; /* ... -
约瑟夫出圈
2010-11-24 20:45 1071#include<iostream> #incl ... -
SmartHashSet只是为了解释HashSet的原理
2010-07-26 11:11 1330写该类的目的只是为了 ... -
二叉树中序遍历非递归算法
2010-06-29 23:17 1691#include<iostream> usi ... -
二叉树的创建
2010-06-29 23:15 1101#include<iostream> usi ... -
哈弗曼树建立与哈弗曼编码
2010-06-29 23:12 1209#include<iostream> #de ... -
二叉排序树转双向链表(要求无任何新增节点)
2010-06-29 23:07 2458题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双 ... -
线索二叉树中插入结点
2010-06-29 23:05 1848#include<iostream> usi ... -
二叉排序树的递归与非递归查找
2010-06-29 22:58 2258#include<iostream> usi ... -
二叉树中序线索化及查找某一结点的前驱,后继结点
2010-06-29 22:54 2643#include<iostream> usi ... -
十字链表定义创建查找
2010-06-29 22:44 1284#include<iostream> #defi ... -
稀疏矩阵转置
2010-06-29 22:39 1600#include<iostream> #defi ... -
单链表实现集合并交差操作
2010-06-29 22:34 1936#include<iostream> usi ...
相关推荐
一个简单的C语言程序:用Trie树实现词频统计和单词查询
用Python实现Trie树的应用,并可以对英汉词典进行导入和检索、添加和删除,最终可以将导入的英汉词典保存到本地磁盘。内附两个.py文件,分别是tree.py和d_gui.py,tree.py是类和方法,d_gui.py是图形界面;一个.txt...
trie.c中定义了trie树的操作函数; trie.h为相应的头文件; test.c用于测试相关的函数。 在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,...
用C实现的数据结构Trie树算法 实验的函数的trie树的插入 搜索和删除
Trie 树实现的源码,用C++编写实现,做自然语言处理的朋友可以参考一下
对双数纽Trie 树(Double-Array Trie)分词算法进行了优化:在采用Trie 树构造 双数纽Trie 树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列; 将冲突的结点放入Hash表中,不需要重新分配...
很容易上手的Trie树入门,特别适合于acm初学者
Double Array Trie是TRIE树的一种变形,它是在保证TRIE树检索速度的前提下,提高空间利用率而提出的一种数据结构,本质上是一个确定有限自动机(deterministic finite automaton,简称DFA)。 所谓的DFA就是一个能实现...
这是一个ACM算法,Trie树,他能很好的解决字符问题
双数组Trie树算法优化及其应用研究.pdf 双数组Trie树算法优化及其应用研究.pdf
网上大神的总结,从trie树谈到后缀树,常用的字符串匹配算法
基于Trie树模仿谷歌百度搜索框提示。写的比较简单、代码漏洞之处欢迎指正。
ACM Trie树 模板,字典树模板,数据结构
2、Trie树SDK中的API支持以下功能 1)插入节点 2)精确删除节点 3)正向模糊匹配 4)反向模糊匹配 5)精确查询节点 6)获取头(尾)节点 7)删除头(尾)节点 8)排序 9)支持多级树 10)支持强大的查询节点功能 ...
trie树模板,acm竞赛,可以进行适当的修改就可以解决问题,在进行字符串处理的时候尤其能用到。
Trie是一种树型数据结构,用于存储字符串,可以实现字符串的快速查找。Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 适用范围:统计和排序大量的字符串
通过基于划分位构建无冲突哈希函数,实现对片上存储器有效的控制,攻击特征平均分配到trie树每层的多个组中。该结构可以在同一个芯片中实现流水并行地执行,获得比较大的吞吐量。理论及实验表明该方法在片上存储器一...
Trie树是搜索树的一种,来自英文单词"Retrieval"的简写,可以建立有效的数据检索组织结构,是中文匹配分词算法中词典的一种常见实现。它本质上是一个确定的有限状态自动机(DFA),每个节点代表自动机的一个状态。在...
hash trie树 字典树,完整的sdk开发包 具有说明文档
IT笔试面试--Trie树前缀树常考题目及解析,包含了Trie树的常考题目,以及详细的解析