#include<bits/stdc++.h>

 using namespace std;

 const int amn=1e5+;

 int trie[amn][],tid;

 bool isw[amn];

 int sum[amn];

 void init(){

     memset(isw,,sizeof isw);

     memset(trie,,sizeof trie);

     memset(sum,,sizeof sum);

     tid=;  ///节点在整个树中的序号

 }

 void insert(char *s){   ///插入一个单词，如果想查询后缀就反向插入

     int len=strlen(s),rt=;

     for(int i=;i<len;i++){

         int id=s[i]-'a';    ///看选择当前节点的哪个儿子

         if(!trie[rt][id])

             trie[rt][id]=++tid;

         sum[rt]++;  ///前缀统计

         rt=trie[rt][id];

     }

     isw[rt]=;  ///结尾单词标记

 }

 bool isword(char *s){   ///查询是否存在这个单词

     int len=strlen(s),rt=;

     for(int i=;i<len;i++){

         int id=s[i]-'a';

         if(!trie[rt][id])return ;

         rt=trie[rt][id];

     }

     return isw[rt];

 }

 bool isprefix(char *s){ ///查询是否存在这个前缀

     int len=strlen(s),rt=;

     for(int i=;i<len;i++){

         int id=s[i]-'a';

         if(!trie[rt][id])return ;

         rt=trie[rt][id];

     }

     return ;

 }

 int prefix_sum(char *s){///查询当前前缀出现的次数

     int len=strlen(s),rt=;

     for(int i=;i<len;i++){

         int id=s[i]-'a';

         if(!trie[rt][id])return ;

         rt=trie[rt][id];

     }

     return sum[rt];

 }

 int main(){

     init();

     char *s="hello",*s1="he";

     insert(s);

     printf("isword:%d isprefix:%d prefix_sum:%d\n",isword(s),isprefix(s1),prefix_sum(s1));

 }