汉字字典树[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

字典树的概念我就不说了，不过大多题目都是英文的字典树，我就闲的蛋疼去写了中文的字典树，实现起来也挺简单的。

#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;
    
}