大家好，又见面了，我是你们的朋友全栈君。
字典树的概念我就不说了，不过大多题目都是英文的字典树，我就闲的蛋疼去写了中文的字典树，实现起来也挺简单的。
代码语言：javascript复制#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <map>
using namespace std;
//字典树，根节点为1
struct Node
{
int length=0;
string lines="";
map<string,int> words;
map<string,int> count;
}tree[1005];
//表示字典树的节点数
int len;
string res[105];
/*char* word(char *aw,int j)
{
char w[105]={' '};
int p=0;
for(int i=j*3;i<j*3 3;i )
{
w[p ]=aw[i];
}
return w;
}
void strcatt(char *as,char *bs,int j)
{
int l=strlen(as);
for(int i=l;i<l 3;i )
{
as[i]=bs[j*3 i-l];
}
}*/
//往字典树立插入字符串
void insert(string a,int i,int j)
{
if(i==a.length()/3)
{
return;
}
if(tree[j].words[a.substr(i*3,3)]!=0)
{
insert(a,i 1,tree[j].words[a.substr(i*3,3)]);
}
else
{
tree[j].words[a.substr(i*3,3)]= len;
tree[j].lines =a.substr(i*3,3);
tree[j].length =3;
if(i==a.length()/3-1)
tree[j].count[a.substr(i*3,3)] ;
insert(a,i 1,len);
}
}
/*
bool equal(char *ae,char *be)
{
if(strlen(ae)!=strlen(be))
return false;
else
{
for(int i=0;i<strlen(ae);i )
{
if(ae[i]!=be[i])
return false;
}
return true;
}
}*/
void remove(Node &s,string x)
{
int y=0;
for(int i=0;i<s.length/3;i )
{
if(s.lines.substr(i*3,3)==x)
{
y=i;break;
}
}
for(int i=y*3;i<s.length;i )
{
s.lines[i]=s.lines[i 3];
}
s.length-=3;
}
//删除字符串
bool del(string a,int i,int j)
{
if(tree[j].words[a.substr(i*3,3)]==0)
return false;
else
{
int x=tree[j].words[a.substr(i*3,3)];
tree[j].words[a.substr(i*3,3)]=0;
remove(tree[j],a.substr(i*3,3));
return del(a,i 1,x);
}
}
//查询某个字符串为前缀的所有词
void QueryPrefix(string a,int i,int j,string str,int &l2)
{
if(i>=a.length()/3)
{
if(tree[j].length==0)
{
return;
}
for(int k=0;k<tree[j].length/3;k )
{
str =tree[j].lines.substr(k*3,3);
if(tree[j].count[tree[j].lines.substr(k*3,3)]!=0)
res[l2 ]=str;
QueryPrefix(a, i 1, tree[j].words[tree[j].lines.substr(k*3,3)],str,l2);
}
}
else if(tree[j].words[a.substr(i*3,3)]==0)
return;
else
{
//strcatt(str,aq,i);
str =a.substr(i*3,3);
if(i==a.length()/3-1)
res[l2 ]=str;
QueryPrefix(a, i 1, tree[j].words[a.substr(i*3,3)],str,l2);
}
}
//查询某个字符串是否存在
bool IsExist(string a,int i,int j)
{
if(i==a.length()/3)
{
return false;
}
if(tree[j].words[a.substr(i*3,3)]==0)
return false;
else
{
if(i==a.length()/3-1&&tree[j].count[a.substr(i*3,3)]!=0)
{
return true;
}
return IsExist(a, i 1,tree[j].words[a.substr(i*3,3)]);
}
}
string input[1005];
int n;
string output;
int main()
{
printf("请输入要插入字典树的字符串数组的长度n");
scanf("%d",&n);
printf("请输入要插入字典树的字符串数组n");
len=1;
for(int i=0;i<n;i )
{
cin>>input[i];
insert(input[i],0,1);
}
printf("请输入keyn");
cin>>output;
printf("查找key是否存在n");
IsExist(output,0, 1);
if(IsExist(output,0,1))
printf("key存在n");
else
printf("key不存在n");
printf("找出所有以key为前缀的字符串n");
string str="";
int l1=0;int l2=0;
QueryPrefix(output, 0, 1,str, l2);
for(int i=0;i<l2;i )
cout<<res[i]<<endl;
printf("key为一句话，找出key中存在的最长词n");
printf("输入keyn");
cin>>output;
int le=output.length();
string xx="";
string ans="";
int res2=0;
for(int i=0;i<le/3;i )
{
for(int l=3;i*3 l<=le;l =3)
{
xx=output.substr(i*3,l);
if(IsExist(xx, 0, 1))
{
if(res2<l)
{
res2=l;
ans=xx;
}
}
}
}
if(res2==0)
{
printf("不存在n");
}
else
{
cout<<ans<<endl;
}
return 0;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
