字典树，是一种树形结构，是一种哈希树的变种。经常被搜索引擎系统用于文本词频统计。
对cat，cash，app，apple，aply，ok 建一颗字典树，建成之后如下图所示
思路
从图中可以直观看出，从左到右扫这个单词，如果字母在相应根节点下没有出现过，就插入这个字母；否则沿着字典树往下走，看单词的下一个字母。
这就产生一个问题：往哪儿插？计算机不会自己选择位置插，我们需要给它指定一个位置，那就需要给每个字母编号。
我们设数组，表示编号为
的节点的第
个孩子是编号为
的节点。
什么意思呢？
这里有2种编号，一种是表示节点的位置编号，这是相对整棵树而言的；另一种是
不理解？看图
还是单词cat，cash，app，apple，aply，ok
我们就按输入顺序对其编第一种号，红色表示编号结果。因为先输入的cat，所以c，a，t分别是1,2,3，然后输入的是cash，因为c，a是公共前缀，所以从s开始编，s是4，以此类推。
注意这里相同字母的编号可能不同(因为它们的父节点不同）
第二种编号，相对节点的编号，紫色表示编号结果。
因为每个节点最多有26个子节点，我们可以按他们的字典序从0——25编号，也就是他们的ASCLL码-a的ASCLL码。
注意这里相同字母的编号相同（减去‘a'肯定一样啊）
回到数组
那么第二种编号即为
字母编号之所以从节点1开始，是因为节点0的第i个孩子是新单词的开始
构建字典树
void init( )
{
pos=1;//初始化，编号为1开始
memset(tree,0,sizeof(tree));//初始化
memset(num,0,sizeof(num));
memset(vis,0,sizeof(vis));
}
void insert(string s)
{
int len=s.size( );
//int len=strlen(s);
int root=0;//新单词root为0，表明是一个新单词，现在知道图中编号要从1开始了吧！！
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
if(!tree[root][x])
{
tree[root][x]=pos;
pos++;
}
root=tree[root][x];
num[root]++;//经过这个节点的单词加一
}
vis[root]=1;//以这个结尾的是一个完整的单词
}
查询
1. 查询在字符串集合中是否有以字符串s为前缀的字符串
int find(char *s)//查找是否有以字符串s为前缀的单词
{
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
if(!tree[root][x])
{
return 0;
}
root=tree[root][x];
}
return 1;
}
2. 查询在字符串集合中有多少个以字符串s为前缀的字符串
int findsum(char *s)//查找以字符串s为前缀的单词有多少个
{
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
if(!tree[root][x])
{
return 0;
}
root=tree[root][x];
}
return num[root];
}
3. 查找并输出每个字符串在字符串集合里面唯一确定的最短前缀（前缀不能有歧义）
Shortest Prefixes
void findminpre(string s)//查找字符串s唯一可以确定的最短前缀
{
//int len=strlen(s);
int len=s.size( );
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
root=tree[root][x];
printf("%c",s[i]);
if(num[root]==1)
{
return ;
}
}
}
4. 判断字符串集合中的字符串否是字符串集合其他字符串的前缀
Phone List
bool judgepremix(char *s)//判断字符串是不是字符串集某个字符串的前缀
{
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
root=tree[root][x];
if(num[root]==1)
{
return 1;//不是某个字符串的前缀
}
}
return 0;
}
5.判断字符串集合中的字符串是否是字符串集合其他两个字符合并的
Hat’s Words
bool findprefix(char *s)//判断字符串是否由串集里的两个字符串构成
{
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
if(!tree[root][x])
{
return 0;
}
root=tree[root][x];
}
return vis[root];
}
完整代码
#include<iostream>
#include<map>
#include<cstring>
#include<cstdio>
using namespace std;
const int M=10010;
int tree[M][26];
int pos;
int num[M];
int vis[M];
map<int,string>mp;
void init( )
{
pos=1;
memset(tree,0,sizeof(tree));
memset(num,0,sizeof(num));
memset(vis,0,sizeof(vis));
}
void insert(string s)
{
int len=s.size( );
//int len=strlen(s);
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
if(!tree[root][x])
{
tree[root][x]=pos;
pos++;
}
root=tree[root][x];
num[root]++;
}
vis[root]=1;//以这个结尾的是一个完整的单词
}
int findsum(char *s)//查找以字符串s为前缀的单词有多少个
{
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
if(!tree[root][x])
{
return 0;
}
root=tree[root][x];
}
return num[root];
}
int find(char *s)//查找是否有以字符串s为前缀的单词
{
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
if(!tree[root][x])
{
return 0;
}
root=tree[root][x];
}
return 1;
}
void findminpre(string s)//查找字符串s唯一可以确定的最短前缀
{
//int len=strlen(s);
int len=s.size( );
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
root=tree[root][x];
printf("%c",s[i]);
if(num[root]==1)
{
return ;
}
}
}
bool judgepremix(char *s)//判断字符串是不是字符串集某个字符串的前缀
{
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
root=tree[root][x];
if(num[root]==1)
{
return 1;//不是某个字符串的前缀
}
}
return 0;
}
bool findprefix(char *s)//判断字符串是否由串集里的两个字符串构成
{
int len=strlen(s);
int root=0;
for(int i=0;i<len;i++)
{
int x=s[i]-'a';
if(!tree[root][x])
{
return 0;
}
root=tree[root][x];
}
return vis[root];
}
int main( )
{
//char s[15];
string s;
init( );
int cnt=0;
while(cin>>s)
{
insert(s);
mp[++cnt]=s;
}
for(int i=1;i<=cnt;i++)
{
cout<<mp[i]<<" ";
findminpre(mp[i]);
cout<<endl;
}
return 0;
}
网友评论