首页 > 代码库 > Trie树基本概念和训练指南
Trie树基本概念和训练指南
接触Trie树是在选拔赛时候遇到一题目,TLE无数次依然无解,赛后发现字符串统计有一利器名曰“字典树”,后来花了一段时间去写Trie,算是基本入门了。
本文主要是介绍一些基本概念,以及一些训练题目,提供大家。
什么叫Trie树?
Trie树即字典树。
又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
(以上来自百度百科)
在我看来,Trie树是一棵26叉树(如果是统计字母的话),典型的空间换时间。那到底我们利用Trie来做什么呢?
1.统计单词
2.匹配前缀
千篇一律地需要提到其性质:
1.根节点不包含字符,除根节点外的每一个子节点都只包含一个字符。
2.从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串
3.每个节点的所有子节点包含的字符都不相同。
而其效率主要体现,通过公共前缀尽可能减少查找复杂度。
其主要操作有:插入,删除,和查询。
插入过程,其实跟普通的树一样。首先我们定义根,根不带表任何字母,对于每一个节点,固定有Size个子节点(字母就是26,数字就是10),一般用固定数组。(malloc浪费时间……)
插入过程,其实跟普通的树一样。首先我们定义根,根不带表任何字母,对于每一个节点,固定有Size个子节点(字母就是26,数字就是10),一般用固定数组。(malloc浪费时间……)
按插入的单词查询每一个字母对应的位置(我的定义字母X对应是第X%26个位置),如果不为null,就更新子节点,查到最后一个字母时候,我们用一个terminable来记载这是结尾,当然插入过程要根据不同题目修改不同的属性值,这在做题目时候就很容易感受到。
查询的操作与插入是很相似的,我们从根开始检索依次查询单词的字母,最后返回相应的信息。
查询很多时候查询分为:有没有?(bool),有多少(int)。这样我们要随着题目改变而改变。
但有时候查询也会在插入时候操作,比如依次插入字母,问是否之前有插入的单词是现在插入的单词的前缀,那么在插入过程中,只要检索在有terminable存在,就返回true(有前缀,注意,这问题必须是前后关系情况,如果是判断插入的单词是否有互为前缀?那么我们就需要保存后(或者排序后),才能逐个查找,因为可能后出现的是前面的前缀)
下面,没拍过字典树的同学就跟着来练习吧!很快你就有感觉了。
查询的操作与插入是很相似的,我们从根开始检索依次查询单词的字母,最后返回相应的信息。
查询很多时候查询分为:有没有?(bool),有多少(int)。这样我们要随着题目改变而改变。
但有时候查询也会在插入时候操作,比如依次插入字母,问是否之前有插入的单词是现在插入的单词的前缀,那么在插入过程中,只要检索在有terminable存在,就返回true(有前缀,注意,这问题必须是前后关系情况,如果是判断插入的单词是否有互为前缀?那么我们就需要保存后(或者排序后),才能逐个查找,因为可能后出现的是前面的前缀)
下面,没拍过字典树的同学就跟着来练习吧!很快你就有感觉了。
首先,发一个模板,我是一个从开始学习语言就写C++的人,所以我在参考了别人后,用模板+类来写,喜欢c风格的同学也可以看看其他人共享的模板。(感觉有点长~但是相对我觉得好理解,假设你知道并且喜欢用template.)
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> using namespace std; template<int Size> struct trie_node { bool terminable; //表示节点为字符串的结尾 int node; //子节点的个数 trie_node *child[Size]; //儿子节点 trie_node():terminable(false), node(0) { memset(child,0,sizeof(child)); //初始化节点 } }; template<int Size,typename Index> class trie { public: //定义类名 typedef trie_node<Size> node_type; typedef trie_node<Size> *link_type; //构造函数 trie(Index i=Index()):index(i) { } void clear() //清空函数,用于析构 { clear_node(root); for(int i=0; i<Size; i++) root.child[i]=0; } template<typename Iterator> void insert(Iterator begin,Iterator end) //插入 { link_type cur= &root;//当前插入结点为根 while(begin!=end) { if(!cur->child[index[*begin]]) //没有插入过 { cur->child[index[*begin]]=new node_type; cur->node++; //插入后,父亲多了一个儿子 } cur=cur->child[index[*begin]]; //搜儿子 begin++; //迭代器往前走! } cur->terminable=true; } void insert(const char * str) //重载c风格插入 { insert(str,str+strlen(str)); } template <typename Iterator> bool find(Iterator begin,Iterator end) //查找 { link_type cur=&root; while(begin!=end) { if(!cur->child[index[*begin]]) //没有节点啊!!! return false; cur=cur->child[index[*begin]]; //搜索儿子 begin++; } return cur->terminable; //是否为字符串 } bool find(const char *str) //重载c风格 { return find(str,str+strlen(str)); } template<typename Iterator> bool earse (Iterator begin,Iterator end) //删除字符串 { bool result; earse_node(begin,end,root,result); return result; } bool erase(char *str) //c语言风格 { return earse(str,str+strlen(str)); } private: void clear_node(node_type cur) //清空 { for(int i=0; i<Size; i++) { if(cur.child[i]==0)continue; //不存在 clear_node(*cur.child[i]); delete cur.child[i]; cur.child[i]=0; if(--cur.node==0) break; //没有节点了 } } //一边搜索一边删除 template<typename Iterator> bool earse_node(Iterator begin ,Iterator end,node_type &cur,bool &result) { if(begin==end) { result=cur.terminable; cur.terminalbe=false; return cur.node==0; } //当孩子不存在,结果假,返回假 if(cur.child[index[*begin ]]==0) return !(result=false); else if(earse_node(begin+1,end,*(cur.child[index[*begin]]),result)) { delete cur.child[index[*begin]]; cur.child[index[*begin]]=0; if(--cur.node==0&&cur.terminable==false ) return true; } return false; } //根 node_type root; //字符转索引,类似hash Index index; }; class IndexClass { public: int operator[](const char key) { return key%26; //一个映射 } }; int main() { trie<26,IndexClass> t; //字母就是26,数字就是10 t.insert("tree"); //插入 t.insert("tea"); t.insert("act"); t.insert("adv"); t.insert("ate"); while(scanf("%s",str)!=EOF)//查找 { if(t.find(str)) { cout<<"find"<<endl; } } return 0; }
之后,怎么少得了经典的问题呢?
HDU1251(统计难题)
http://acm.hdu.edu.cn/showproblem.php?pid=1251
字典树做这些问题就是神器啊。注意统计的时候,node的处理,也就是insert和find的一些改变。
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> using namespace std; template<int Size> struct trie_node { bool terminable; //表示节点为字符串的结尾 int node; //子节点的个数 trie_node *child[Size]; //儿子节点 trie_node():terminable(false), node(0) { memset(child,0,sizeof(child)); //初始化节点 } }; template<int Size,typename Index> class trie { public: //定义类名 typedef trie_node<Size> node_type; typedef trie_node<Size> *link_type; //构造函数 trie(Index i=Index()):index(i) { } void clear() //清空函数,用于析构 { clear_node(root); for(int i=0; i<Size; i++) root.child[i]=0; } //插入 template<typename Iterator> void insert(Iterator begin,Iterator end){ link_type cur= &root;//当前插入结点为根 while(begin!=end){ if(cur->child[index[*begin]]){//插入过 cur=cur->child[index[*begin]]; ++(cur->node); }else{ cur->child[index[*begin]]=new node_type; //这里这里!!!不一样!!!! ++(cur->child[index[*begin]]->node); cur=cur->child[index[*begin]]; } begin++; //迭代器往前走! } cur->terminable=true; } void insert(const char * str) //重载c风格插入 { insert(str,str+strlen(str)); } template <typename Iterator> bool find(Iterator begin,Iterator end) //查找 { link_type cur=&root; while(begin!=end) { if(!cur->child[index[*begin]]) //没有节点啊!!! return false; cur=cur->child[index[*begin]]; //搜索儿子 begin++; } return cur->terminable; //是否为字符串 } bool find(const char *str) //重载c风格 { return find(str,str+strlen(str)); } template <typename Iterator> int findNum(Iterator begin,Iterator end){ link_type cur=&root; while(begin!=end){ if(!cur->child[index[*begin]]) //没有节点啊!!! return 0; cur=cur->child[index[*begin]]; begin++; } return cur->node; //是否为字符串 } //重载c风格 int findNum(const char *str){ return findNum(str,str+strlen(str)); } template<typename Iterator> bool earse (Iterator begin,Iterator end) //删除字符串 { bool result; earse_node(begin,end,root,result); return result; } bool erase(char *str) //c语言风格 { return earse(str,str+strlen(str)); } private: void clear_node(node_type cur) //清空 { for(int i=0; i<Size; i++) { if(cur.child[i]==0)continue; //不存在 clear_node(*cur.child[i]); delete cur.child[i]; cur.child[i]=0; if(--cur.node==0) break; //没有节点了 } } //一边搜索一边删除 template<typename Iterator> bool earse_node(Iterator begin ,Iterator end,node_type &cur,bool &result) { if(begin==end) { result=cur.terminable; cur.terminalbe=false; return cur.node==0; } //当孩子不存在,结果假,返回假 if(cur.child[index[*begin ]]==0) return !(result=false); else if(earse_node(begin+1,end,*(cur.child[index[*begin]]),result)) { delete cur.child[index[*begin]]; cur.child[index[*begin]]=0; if(--cur.node==0&&cur.terminable==false ) return true; } return false; } //根 node_type root; //字符转索引,类似hash Index index; }; class IndexClass { public: int operator[](const char key) { return key%26; //一个映射 } }; int main(){ trie<26,IndexClass> t; char s[11]; while(gets(s) && s[0]) { t.insert( s); } while(gets(s)) { printf("%d\n", t.findNum(s)); } return 0; }
HDU1671
http://acm.hdu.edu.cn/showproblem.php?pid=1671
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> #include<vector> using namespace std; #define MAXN 10 template<int Size> struct trie_node { bool terminable; //表示节点为字符串的结尾 int node; //子节点的个数 trie_node *child[Size]; //儿子节点 trie_node():terminable(false), node(0) { memset(child,0,sizeof(child)); //初始化节点 } }; template<int Size,typename Index> class trie { public: //定义类名 typedef trie_node<Size> node_type; typedef trie_node<Size> *link_type; //构造函数 trie(Index i=Index()):index(i) { } //清空函数,用于析构 void clear() { clear_node(root); for(int i=0; i<Size; i++) root.child[i]=0; } //插入 template<typename Iterator> void insert(Iterator begin,Iterator end) { link_type cur= &root;//当前插入结点为根 while(begin!=end) { if(cur->child[index[*begin]]) //插入过 { cur=cur->child[index[*begin]]; cur->node++; } else { cur->child[index[*begin]]=new node_type; cur->child[index[*begin]]->node++; cur=cur->child[index[*begin]]; } begin++; //迭代器往前走! } cur->terminable=true; } //重载c风格插入 void insert(const char * str) { insert(str,str+strlen(str)); } //插入 template<typename Iterator> bool insert2(Iterator begin,Iterator end) { link_type cur= &root;//当前插入结点为根 bool flag=0; while(begin!=end) { if(cur->child[index[*begin]]) //插入过 { if(cur->child[index[*begin]]->terminable==true){ flag=1; } cur=cur->child[index[*begin]]; cur->node++; } else { cur->child[index[*begin]]=new node_type; cur->child[index[*begin]]->node++; cur=cur->child[index[*begin]]; } begin++; //迭代器往前走! } cur->terminable=true; return flag; } //重载c风格插入 bool insert2(const char * str) { return insert2(str,str+strlen(str)); } //查找 template <typename Iterator> bool find(Iterator begin,Iterator end) { link_type cur=&root; while(begin!=end) { if(!cur->child[index[*begin]]) //没有节点啊!!! return false; cur=cur->child[index[*begin]]; begin++; } return cur->terminable; //是否为字符串 } //重载c风格 bool find(const char *str) { return find(str,str+strlen(str)); } //查找节点数目 template <typename Iterator> int findNum(Iterator begin,Iterator end) { link_type cur=&root; while(begin!=end) { if(!cur->child[index[*begin]]) //没有节点啊!!! return 0; cur=cur->child[index[*begin]]; begin++; } return cur->node; //是否为字符串 } //重载c风格 int findNum(const char *str) { return findNum(str,str+strlen(str)); } //查找前缀 template <typename Iterator> bool findPre(Iterator begin,Iterator end) { link_type cur=&root; while(begin!=end) { if(!cur->child[index[*begin]]) //没有节点啊!!! return false; if(cur->terminable) break; cur=cur->child[index[*begin]]; begin++; } return begin!=end; //是否为字符串 } bool findPre(const char *str){ return findPre(str,str+strlen(str)); } //删除字符串 template<typename Iterator> bool earse (Iterator begin,Iterator end) { bool result; earse_node(begin,end,root,result); return result; } //c语言风格 bool erase(char *str) { return earse(str,str+strlen(str)); } template<typename Functor> void traverse(Functor &execute =Functor()) { visit_node(root,execute); } private: //访问结点 template<typename Functor> void visit_node(node_type cur,Functor &execute) { execute(cur); for(int i=0; i<Size; i++) //dfs { if(cur.child[i]==0) continue; visit_node(*cur.child[i],execute); } } //清空 void clear_node(node_type cur) { for(int i=0; i<Size; i++) { if(cur.child[i]==0)continue; //不存在 clear_node(*cur.child[i]); delete cur.child[i]; cur.child[i]=0; if(--cur.node==0) break; //没有节点了 } } //一边搜索一边删除 template<typename Iterator> bool earse_node(Iterator begin ,Iterator end,node_type &cur,bool &result) { if(begin==end) { result=cur.terminable; cur.terminalbe=false; return cur.node==0; } //当孩子不存在,结果假,返回假 if(cur.child[index[*begin ]]==0) return !(result=false); else if(earse_node(begin+1,end,*(cur.child[index[*begin]]),result)) { delete cur.child[index[*begin]]; cur.child[index[*begin]]=0; if(--cur.node==0&&cur.terminable==false ) return true; } return false; } //根 node_type root; //字符转索引,类似hash Index index; }; class IndexClass { public: int operator[](const char key) { return key%MAXN; //一个映射 } }; char s[10000][11]; int main() { trie<MAXN,IndexClass> t; int T,n,i; // freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { scanf("%d",&n); t.clear(); for(i=0;i<n;i++){ scanf("%s",s[i]); t.insert(s[i]); } for(i=0;i<n;i++){ if(t.findPre(s[i])){ puts("NO"); break; } } if(i==n) puts("YES"); } return 0; }
HDU1004,或许你用map水过去了,但是你不妨试试用字典树获取0ms吧!(我的代码注释忽略吧,linux的编码跟windows有差距啊……)
http://acm.hdu.edu.cn/showproblem.php?pid=1004
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> using namespace std; template<int Size> struct trie_node{ bool terminable; //??????????? int node; //?????? int cnt; trie_node *child[Size]; //???? trie_node():terminable(false), node(0),cnt(0){ memset(child,0,sizeof(child)); //????? } }; int maxN; char sb[30]; char s[30]; template<int Size,typename Index> class trie{ public: //???? typedef trie_node<Size> node_type; typedef trie_node<Size> *link_type; //???? trie(Index i=Index()):index(i){ } //????,???? void clear(){ clear_node(root); for(int i=0;i<Size;i++) root.child[i]=0; } //?? template<typename Iterator> bool insert(Iterator begin,Iterator end){ link_type cur= &root;//???????? while(begin!=end){ if(!cur->child[index[*begin]]){//??? cur->child[index[*begin]]=new node_type; cur->node++; } cur=cur->child[index[*begin]]; begin++; //??????! } cur->terminable=true; cur->cnt++; if(cur->cnt> maxN){ maxN=cur->cnt; // cout<<maxN; return true; } return false; } //??c???? void insert( char * str){ if(insert(str,str+strlen(str))){ strcpy(sb,str); }; } private: //?? void clear_node(node_type cur){ for(int i=0;i<Size;i++){ if(cur.child[i]==0)continue; //??? clear_node(*cur.child[i]); delete cur.child[i]; cur.child[i]=0; if(--cur.node==0) break; //????? } } //? node_type root; //?????,??hash Index index; }; class IndexClass{ public: int operator[](const char key){ return key%26; //???? } }; int main(){ trie<26,IndexClass> t; //freopen("in.txt","r",stdin); int n; while(scanf("%d",&n)&&n) { maxN=-1; for(int i=0;i<n;i++){ scanf("%s",s); t.insert(s); // cout<<maxN<<endl; } printf("%s\n",sb); t.clear(); } return 0; }
HDU1075
http://acm.hdu.edu.cn/showproblem.php?pid=1075
这题目还是很赤裸的字典树,但是我犯了一个小错,让我WA无数次。
ACcode:
ACcode:
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> using namespace std; char str1[12]; char str2[12]; char st[3100]; template<int Size> struct trie_node { bool terminable; //表示节点为字符串的结尾 int node; //子节点的个数 char str[12]; trie_node *child[Size]; //儿子节点 trie_node():terminable(false), node(0) { memset(child,0,sizeof(child)); //初始化节点 } }; template<int Size,typename Index> class trie { public: //定义类名 typedef trie_node<Size> node_type; typedef trie_node<Size> *link_type; //构造函数 trie(Index i=Index()):index(i) { } //清空函数,用于析构 void clear() { clear_node(root); for(int i=0; i<Size; i++) root.child[i]=0; } //插入 template<typename Iterator> void insert(Iterator begin,Iterator end) { link_type cur= &root;//当前插入结点为根 while(begin!=end) { if(cur->child[index[*begin]]) //插入过 { cur=cur->child[index[*begin]]; ++(cur->node); } else { cur->child[index[*begin]]=new node_type; ++(cur->child[index[*begin]]->node); cur=cur->child[index[*begin]]; } begin++; //迭代器往前走! } cur->terminable=true; int len=strlen(str1); for(int i=0; i<=len; i++) cur->str[i]=str1[i]; } //重载c风格插入 void insert(const char * str) { insert(str,str+strlen(str)); } //查找 template <typename Iterator> bool find(Iterator begin,Iterator end) { link_type cur=&root; while(begin!=end) { if(!cur->child[index[*begin]]) //没有节点啊!!! return false; cur=cur->child[index[*begin]]; begin++; } // printf("%s sb",cur->str); if(cur->terminable) { printf("%s",cur->str); return true; } return false; //是否为字符串 } //重载c风格 bool find(const char *str) { return find(str,str+strlen(str)); } private: //清空 void clear_node(node_type cur) { for(int i=0; i<Size; i++) { if(cur.child[i]==0)continue; //不存在 clear_node(*cur.child[i]); delete cur.childe[i]; cur.child[i]=0; if(--cur.node==0) break; //没有节点了 } } //根 node_type root; //字符转索引,类似hash Index index; }; class IndexClass { public: int operator[](const char key) { return key%26; //一个映射 } }; int main() { trie<26,IndexClass> t; scanf("%s",str2) ; while(scanf("%s",str1)) { if(str1[0]==‘E‘) { break; } scanf("%s",str2); t.insert(str2); } scanf("%s",str2); getchar(); while(gets(st)) { if(st[0]==‘E‘) { break; } int len=strlen(st); int bg=0; for(int i=0; i<len; i++) { if(st[i]>=‘a‘&&st[i]<=‘z‘) { continue; } if(!t.find(st+bg,st+i)) { for(int j=bg; j<i; j++) printf("%c",st[j]); }; if(st[i]) printf("%c",st[i]); bg=i+1; } puts(""); } return 0; }WAcode:
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> using namespace std; char str1[12]; char str2[12]; char st[3100]; template<int Size> struct trie_node { bool terminable; //表示节点为字符串的结尾 int node; //子节点的个数 char str[12]; trie_node *child[Size]; //儿子节点 trie_node():terminable(false), node(0) { memset(child,0,sizeof(child)); //初始化节点 } }; template<int Size,typename Index> class trie { public: //定义类名 typedef trie_node<Size> node_type; typedef trie_node<Size> *link_type; //构造函数 trie(Index i=Index()):index(i) { } //清空函数,用于析构 void clear() { clear_node(root); for(int i=0; i<Size; i++) root.child[i]=0; } //插入 template<typename Iterator> void insert(Iterator begin,Iterator end) { link_type cur= &root;//当前插入结点为根 while(begin!=end) { if(cur->child[index[*begin]]) //插入过 { cur=cur->child[index[*begin]]; ++(cur->node); } else { cur->child[index[*begin]]=new node_type; ++(cur->child[index[*begin]]->node); cur=cur->child[index[*begin]]; } begin++; //迭代器往前走! } cur->terminable=true; int len=strlen(str1); for(int i=0; i<len; i++) cur->str[i]=str1[i]; } //重载c风格插入 void insert(const char * str) { insert(str,str+strlen(str)); } //查找 template <typename Iterator> bool find(Iterator begin,Iterator end) { link_type cur=&root; while(begin!=end) { if(!cur->child[index[*begin]]) //没有节点啊!!! return false; cur=cur->child[index[*begin]]; begin++; } // printf("%s sb",cur->str); if(cur->terminable) { printf("%s",cur->str); return true; } return false; //是否为字符串 } //重载c风格 bool find(const char *str) { return find(str,str+strlen(str)); } private: //清空 void clear_node(node_type cur) { for(int i=0; i<Size; i++) { if(cur.child[i]==0)continue; //不存在 clear_node(*cur.child[i]); delete cur.childe[i]; cur.child[i]=0; if(--cur.node==0) break; //没有节点了 } } //根 node_type root; //字符转索引,类似hash Index index; }; class IndexClass { public: int operator[](const char key) { return key%26; //一个映射 } }; int main() { trie<26,IndexClass> t; scanf("%s",str2) ; while(scanf("%s",str1)) { if(str1[0]==‘E‘) { break; } scanf("%s",str2); t.insert(str2); } scanf("%s",str2); getchar(); while(gets(st)) { if(st[0]==‘E‘) { break; } int len=strlen(st); int bg=0; for(int i=0; i<len; i++) { if(st[i]>=‘a‘&&st[i]<=‘z‘) { continue; } if(!t.find(st+bg,st+i)) { for(int j=bg; j<i; j++) printf("%c",st[j]); }; if(st[i]) printf("%c",st[i]); bg=i+1; } puts(""); } return 0; }
(差别就在字符串copy 上没有拷贝上‘\0‘……,也就是st[len])
HDU1247
http://acm.hdu.edu.cn/showproblem.php?pid=1247
题目相对理解上会有点偏差,不是当且仅当两个,是两个,举个例子
a
abc
b
bc
c
输出的是:abc,bc(注意abc也是,不要因为abc=a+b+c,而忽略,只要可以满足s=s1+s2即可,即abc=a+bc,bc=b+c)
其实我就是用了字典树+dfs
另外,记得有一题目是:
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<cstdlib> using namespace std; template<int Size> struct trie_node{ bool terminable; //表示节点为字符串的结尾 int node; //子节点的个数 trie_node *child[Size]; //儿子节点 trie_node():terminable(false), node(0){ memset(child,0,sizeof(child)); //初始化节点 } }; template<int Size,typename Index> class trie{ public: //定义类名 typedef trie_node<Size> node_type; typedef trie_node<Size> *link_type; //构造函数 trie(Index i=Index()):index(i){ } //清空函数,用于析构 void clear(){ clear_node(root); for(int i=0;i<Size;i++) root.child[i]=0; } //插入 template<typename Iterator> void insert(Iterator begin,Iterator end){ link_type cur= &root;//当前插入结点为根 while(begin!=end){ if(cur->child[index[*begin]]){//插入过 cur=cur->child[index[*begin]]; ++(cur->node); }else{ cur->child[index[*begin]]=new node_type; ++(cur->child[index[*begin]]->node); cur=cur->child[index[*begin]]; } // cout<<*begin; begin++; //迭代器往前走! } cur->terminable=true; // cout<<cur->id<<endl; } //重载c风格插入 void insert(const char * str){ insert(str,str+strlen(str)); } //查找 template <typename Iterator> bool find(Iterator begin,Iterator end){ link_type cur=&root; while(begin!=end){ if(!cur->child[index[*begin]])return false; //我在这里re了无数次…忧桑…… cur=cur->child[index[*begin]]; begin++; } // cout<<*begin<<" "<<*end<<"sb" <<endl; return cur->terminable; } //重载c风格 bool find(const char *str){ return find(str,str+strlen(str)); } private: //清空 void clear_node(node_type cur){ for(int i=0;i<Size;i++){ if(cur.child[i]==0)continue; //不存在 clear_node(*cur.child[i]); delete cur.childe[i]; cur.child[i]=0; if(--cur.node==0) break; //没有节点了 } } //根 node_type root; //字符转索引,类似hash Index index; }; class IndexClass{ public: int operator[](const char key){ return key%26; //一个映射 } }; char str[50005][100]; int main(){ trie<26,IndexClass> t; int i=0; while(scanf("%s",str[i])!=EOF){ // cout<<str[i]; t.insert(str[i]); i++; } for(int j=0;j<i;j++){ int len=strlen(str[j]); for(int p=1;p<=len-1;p++){ if(t.find(str[j],str[j]+p)){ if(t.find(str[j]+p)){ printf("%s\n",str[j]); break; } } } } return 0; }尽管我上面这个做法已经OK了,但是这是参考了别人,下面是我完全按自己想法写的,程序员最高兴的莫过于可以将自己的想法实现。
其实我就是用了字典树+dfs
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<cstdlib> using namespace std; template<int Size> struct trie_node{ bool terminable; //表示节点为字符串的结尾 int node; //子节点的个数 trie_node *child[Size]; //儿子节点 trie_node():terminable(false), node(0){ memset(child,0,sizeof(child)); //初始化节点 } }; template<int Size,typename Index> class trie{ public: //定义类名 typedef trie_node<Size> node_type; typedef trie_node<Size> *link_type; //构造函数 trie(Index i=Index()):index(i){ } //清空函数,用于析构 void clear(){ clear_node(root); for(int i=0;i<Size;i++) root.child[i]=0; } //插入 template<typename Iterator> void insert(Iterator begin,Iterator end){ link_type cur= &root;//当前插入结点为根 while(begin!=end){ if(cur->child[index[*begin]]){//插入过 cur=cur->child[index[*begin]]; ++(cur->node); }else{ cur->child[index[*begin]]=new node_type; ++(cur->child[index[*begin]]->node); cur=cur->child[index[*begin]]; } // cout<<*begin; begin++; //迭代器往前走! } cur->terminable=true; // cout<<cur->id<<endl; } //重载c风格插入 void insert(const char * str){ insert(str,str+strlen(str)); } //查找 template <typename Iterator> bool find(Iterator begin,Iterator end,int i){ link_type cur=&root; while(begin!=end){ if(cur->terminable){ if(i>1) return false; if( find(begin,end,i+1))return true; } if(!cur->child[index[*begin]]) return false; cur=cur->child[index[*begin]]; begin++; } if(!cur->terminable){ return false; } return i==1; } //重载c风格 bool find(const char *str,int i){ return find(str,str+strlen(str),i); } private: //清空 void clear_node(node_type cur){ for(int i=0;i<Size;i++){ if(cur.child[i]==0)continue; //不存在 clear_node(*cur.child[i]); delete cur.child[i]; cur.child[i]=0; if(--cur.node==0) break; //没有节点了 } } //根 node_type root; //字符转索引,类似hash Index index; }; class IndexClass{ public: int operator[](const char key){ return key%26; //一个映射 } }; char str[50005][50]; int main(){ trie<26,IndexClass> t; int i=0; //freopen("in.txt","r",stdin); while(scanf("%s",str[i])!=EOF){ // cout<<str[i]; t.insert(str[i]); i++; } for(int j=0;j<i;j++){ if(t.find(str[j],0)){ //类似与dfss printf("%s\n",str[j]); } } return 0; }
HDU1857,逆向思维的trie,可以参考我之前写过的
http://acm.hdu.edu.cn/showproblem.php?pid=1857
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<cmath> #include<cstdlib> using namespace std; template<int Size> struct trie_node{ bool terminable; //表示节点为字符串的结尾 int node; //子节点的个数 int id; trie_node *child[Size]; //儿子节点 trie_node():terminable(false), node(0){ memset(child,0,sizeof(child)); //初始化节点 } }; int RR[10200],CC[10200]; template<int Size,typename Index> class trie{ public: //定义类名 typedef trie_node<Size> node_type; typedef trie_node<Size> *link_type; //构造函数 trie(Index i=Index()):index(i){ } //清空函数,用于析构 void clear(){ clear_node(root); for(int i=0;i<Size;i++) root.child[i]=0; } //插入 template<typename Iterator> void insert(Iterator begin,Iterator end,int i){ link_type cur= &root;//当前插入结点为根 while(begin!=end){ if(cur->child[index[*begin]]){//插入过 cur=cur->child[index[*begin]]; ++(cur->node); }else{ cur->child[index[*begin]]=new node_type; ++(cur->child[index[*begin]]->node); cur=cur->child[index[*begin]]; } begin++; //迭代器往前走! } cur->terminable=true; cur->id=i; } //重载c风格插入 void insert(const char * str,int i){ insert(str,str+strlen(str), i); } //查找 template <typename Iterator> void find(Iterator begin,Iterator end,int r,int c){ link_type cur=&root; while(begin!=end){ if(cur->terminable){ if(RR[cur->id]==0){ RR[cur->id]=r; CC[cur->id]=c; } } if(!cur->child[index[*begin]]) //没有节点啊!!! return ; cur=cur->child[index[*begin]]; begin++; } if( cur->terminable) {//是否为字符串 if(RR[cur->id]==0){ RR[cur->id]=r; CC[cur->id]=c; } } } //重载c风格 void find(const char *str,int r,int c){ find(str,str+strlen(str),r,c); } private: //清空 void clear_node(node_type cur){ for(int i=0;i<Size;i++){ if(cur.child[i]==0)continue; //不存在 clear_node(*cur.child[i]); delete cur.childe[i]; cur.child[i]=0; if(--cur.node==0) break; //没有节点了 } } //根 node_type root; //字符转索引,类似hash Index index; }; class IndexClass{ public: int operator[](const char key){ return key%26; //一个映射 } }; char cc[501][501]; char s[21]; int mini(int a,int b){ return a>b?b:a; } int main(){ trie<26,IndexClass> t; int R,C,i,j,l,ed; scanf("%d%d",&R,&C); getchar(); //读掉回车 for( i=0;i<R;i++) { gets(cc[i]); } int N=0; while(gets(s)&&s[0]!=‘-‘){ if(s[0]){ t.insert(s,N); //用每一个要查找的单词构树 N++; } } for(i=0;i<R;i++) for( j=0;j<C;j++){ //向下 memset(s,0,sizeof(s)); if(i+20<R) ed=20; else ed=R-i; for(l=0;l<ed;l++){ s[l]=cc[i+l][j]; } t.find(s,i+1,j+1); //向右 memset(s,0,sizeof(s)); if(j+20<C) ed=20; else ed=C-j; for( l=0;l<ed;l++){ s[l]=cc[i][j+l]; } t.find(s,i+1,j+1); //右下 memset(s,0,sizeof(s)); if(i+20<R&&j+20<C) ed=20; else ed=mini(C-j,R-i); for( l=0;l<ed;l++){ s[l]=cc[i+l][j+l]; } t.find(s,i+1,j+1); } for( i=0;i<N;i++){ if(RR[i]!=0||CC[i]!=0) printf("%d %d\n",RR[i]-1,CC[i]-1); else puts("-1 -1"); } return 0; }
另外,记得有一题目是:
给你一些32位内整数(数字大概在100000左右),我们找这些数中两个使得异或值最大,以前我是没有什么头绪的,n^2算法是必超无疑问的。那现在利用字典树应该能更快地解答这个问题。首先,将数字补全到32位(前面补0)
建树的过程就是,将补全后的数字全插入,之后对于每一个数字取反后去匹配查找(如果有的话,就为1,没的话就为0,进入到有的节点继续查询),这样就可以得到一个max值了。
记得在高校俱乐部曾经有一题也是类似的,就是异或值大于K的数有多少对,当时我也没想到很好的办法,后来,其实就是在查询时候加上判断是否大于K即可。
至于实现我还没有写。因为最近在拍计算几何了,周末就是GDCPC了,很期待省赛!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。