汉字字典树[通俗易懂]

#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]={'\0'};
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("请输入key\n");
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("输入key\n");
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;
}