字典树【知识点+模板】

模版链接
建树 的过程剖析

#include 
using namespace std;
#define inf 0x3f3f3f3f
#define LL long long
const int MAXN = 100000;
const int MAXM = 1e6+100;
const double PI = acos(-1.0);
const double eps = 1e-8;
inline int read(){
    int x=0,f=1; char ch=getchar();
    while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}
/*--------------------------------------*/
 // MAX 记录总节点的数目 
char str[1010][50];//输入的字符串集 
int ch[MAX][30];//字典树的实现 
int word[MAX];//记录当前节点下有多少个单词 
int val[MAX];//标记单词节点 
int sz;//节点数
//初始化 
void init()  
{  
    sz = 1;  
    memset(ch[0], 0, sizeof(ch[0]));  
    memset(word, 0, sizeof(word));  
}   
// 返回字符的ascll码值： 
int idx(char x)  
{  
    return x - 'a';  
}  
//插入字符串：
void insert(char *s)
{
    int i, j, len = strlen(s);
    int u = 0;//根节点开始 
    for(i = 0; i     {
        int c = idx(s[i]);
        if(!ch[u][c])//当前节点不存在 
        {
            memset(ch[sz], 0, sizeof(ch[sz]));//初始化新节点 
            val[sz] = 0;
            ch[u][c] = sz++; //节点数增一 
        }
        u = ch[u][c];
        word[u]++;//单词数加一 
    }
    val[u] = 1;//标记单词节点 
}
//查找以字符串s为前缀的字符串 在字符串集中有多少个
int findnum(char *s)//查询以该s为前缀的字符串有多少个 
{    
    int i, j, l = strlen(s);    
    int u = 0;    
    for(i = 0; i     {    
        int c = idx(s[i]);    
        if(!ch[u][c]) return 0;//不存在 
        u = ch[u][c];    
    }    
    return word[u];    
}    
//查找并输出字符串在串集里面唯一确定的最短前缀 ：
void findprefix(char *s)  
{  
    int i, j, len = strlen(s);  
    int u = 0;  
    for(i = 0; i     {  
        int c = idx(s[i]);  
        u = ch[u][c];//继续查找 
        printf("%c", s[i]);  
        if(word[u] == 1)//节点下只有一个单词 
        return ;  
    }   
}   
//判断该字符串是不是串集里某个字符串前缀 ：
bool judgeprefix(char *s)  
{  
    int i, j, len = strlen(s);  
    int u = 0;  
    for(i = 0; i     {  
        int c = idx(s[i]);  
        u = ch[u][c];//继续查找 
        if(word[u] == 1)//不是任何字符串的前缀 
        return true;  
    }   
    return false;//是前缀 
}   
//判断字符串是否由串集里的两个字符串构成： 假设该字符串分s1,s2两部分，这里只实现s1的查找
bool finds(char *s)  
{  
    int i, j, len = strlen(s);  
    int u = 0;  
    for(i = 0; i     {  
        int c = idx(s[i]);  
        if(!ch[u][c])//不存在节点 
        return false;  
        u = ch[u][c];  
    }  
    return val[u];//最后一个是不是单词节点 
}  

int main()
{

    return 0;
}