字典树

男娘i 2021-11-09 15:52 313阅读 0赞

### 字典树 ###

*  前言
 *  利用指针实现
 *  用数组实现

# 前言 #

介绍

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅
    限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少
    无谓的字符串比较，查询效率比哈希树高。

性质

(1) 根节点不包含字符，除根节点外每一个节点都只包含一个字符；
    (2) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
    (3) 每个节点的所有子节点包含的字符都不相同。

应用

(1）字符串检索。Trie树的基本功能。
    (2）词频统计。统计一个单词出现了多少次。
    (3）字符串排序。插入的时候，在树的平级，按字母表的顺序插入。Trie树建好后，用先序遍历，就得到了字典序的排序。
    (4）前缀匹配。Trie树是按公共前缀来建树的，很适合用于搜索提示。例如linux的行命令，输入一个命令的前面几个字母，系统会自
    动补全命令后面的字符。

# 利用指针实现 #

#include<bits/stdc++.h>
    using namespace std;
    const int N = 26;//只包含26个小写字母的字符串
    
    /* 字典树： */
    
    struct Trie{ 
    	Trie* next[26];//指针实现容易占用大量空间
    	int num;//以当前字符串为前缀的单词数量
    	Trie(){ 
    		for(int i=0;i<N;i++)next[i]=nullptr;
    		num = 0;
    	}
    };
    
    Trie root;
    void insert(char str[]){ //将一个字符串插入到字典树中
    	Trie*p=&root;
    	for(int i=0;str[i];i++){ 
    		if(p->next[str[i]-'a']==nullptr)
    		    p->next[str[i]-'a']==new Trie();
    		p = p->next[str[i]-'a'];
    		p->num++;
    	}
    }
    
    int find(char str[]){ 
    	Trie*p=&root;
    	for(int i=0;str[i];i++){ 
    		if(p->next[str[i]-'a']==nullptr)return a;
    		p = p->next[str[i]-'a'];
    	}
    	return p->num;
    }
    
    int main(){ 
    	char str[11];
    	while(gets(str)){ 
    		if(!str[0])break;//输入一个空行
    		insert(str);
    	}
    	while(gets(str))cout<<find(str)<<endl;
    	return 0;
    }

# 用数组实现 #

#include<bits/stdc++.h>
    using namespace std;
    const int N = 26;//只包含26个小写字母的字符串
    const int maxn = 1e6+10;
    
    /* 字典树： */
    
    int trie[maxn][N];//存储下一个字符的位置
    int num[maxn];//存储某一个字符串为前缀的单词的数量
    int pos =1;//单前新分配的存储位置
    void insert(char str[]){ //将一个字符串插入到字典树中
        int p =0;
    	for(int i=0;str[i];i++){ 
    		int n = str[i-'a'];
    		if(trie[p][n]==0)trie[p][n]=pos++;
    		p=trie[p][n];
    		num[p]++;
    	}
    }
    
    int find(char str[]){ 
    	int p =0;
    	for(int i=0;str[i];i++){ 
    	    int n = str[i-'a'];
    		if(trie[p][n]==0)return 0;
    		p=trie[p][n];
    	}
    	return num[p];
    }
    
    int main(){ 
    	char str[11];
    	while(gets(str)){ 
    		if(!str[0])break;//输入一个空行
    		insert(str);
    	}
    	while(gets(str))cout<<find(str)<<endl;
    	return 0;
    }