推荐几篇博客：https://www.cnblogs.com/TheRoadToTheGold/p/6290732.html 浅谈Trie树
https://blog.csdn.net/u013588639/article/details/38406453 字典树的数组实现
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn=200010; 6 int ch[maxn][27],val[maxn]; 7 int sz; 8 9 void init()10 {11 sz=0;12 memset(ch,0,sizeof(ch));13 memset(val,0,sizeof(val));14 }15 16 void insert(char *s)17 {18 int u=0,c;19 for ( int i=0;s[i];i++ )20 {21 c=s[i]-'a';22 if ( !ch[u][c] ) ch[u][c]=++sz;23 u=ch[u][c];24 val[u]++;25 }26 }27 28 int query(char *s)29 {30 int u=0,c;31 for ( int i=0;s[i];i++ )32 {33 c=s[i]-'a';34 if ( !ch[u][c] ) return 0;35 u=ch[u][c];36 }37 return val[u];38 }
练习题：
1.（HDOJ1251）http://acm.hdu.edu.cn/showproblem.php?pid=1251
分析：模板题，注意数组要开大不然会RE
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn=500010; 6 int ch[maxn][27],val[maxn]; 7 int sz; 8 char s[15]; 9 10 void init()11 {12 sz=0;13 memset(ch,0,sizeof(ch));14 memset(val,0,sizeof(val));15 }16 17 void insert(char *s)18 {19 int u=0,c;20 for ( int i=0;s[i];i++ )21 {22 c=s[i]-'a';23 if ( !ch[u][c] ) ch[u][c]=++sz;24 u=ch[u][c];25 val[u]++;26 }27 }28 29 int query(char *s)30 {31 int u=0,c;32 for ( int i=0;s[i];i++ )33 {34 c=s[i]-'a';35 if ( !ch[u][c] ) return 0;36 u=ch[u][c];37 }38 return val[u];39 }40 41 int main()42 {43 int i,j,k;44 bool flag=true;45 init();46 while ( gets(s) ) 47 {48 if ( flag )49 {50 if ( strlen(s)!=0 ) insert(s);51 else flag=false;52 }53 else printf("%d\n",query(s));54 }55 return 0;56 }
2.（HDOJ1671）http://acm.hdu.edu.cn/showproblem.php?pid=1671
题意：是否有一个电话号码是另一个电话号码的前缀
分析：可以将更新和查询放到同一个数组中进行，开一个bool型的数组isw记录该编号的节点是否为单词的结尾（可以解决前缀先输入的情况）。而对于前缀后输入的情况，在插入时设置一个bool型的变量ok，判断在整个插入过程是否有申请过新的节点
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn=5e5+10; 6 int ch[maxn][11]; 7 int sz; 8 bool isw[maxn],flag; 9 char s[105];10 11 void init()12 {13 sz=0;14 flag=false;15 memset(ch,0,sizeof(ch));16 memset(isw,false,sizeof(isw));17 }18 19 void insert(char *s)20 {21 int u=0,c;22 bool ok=false;23 for ( int i=0;s[i];i++ )24 {25 c=s[i]-'0';26 if ( !ch[u][c] ) {27 ch[u][c]=++sz;28 ok=true;29 }30 u=ch[u][c];31 if ( isw[u] ) flag=true;32 }33 isw[u]=true;34 if ( !ok ) flag=true;35 }36 37 int main()38 {39 int T,n,m,i,j,k,x,y,z;40 scanf("%d",&T);41 while ( T-- )42 {43 scanf("%d",&n);44 init();45 for ( i=1;i<=n;i++ ) 46 {47 scanf("%s",s);48 insert(s);49 }50 if ( flag ) printf("NO\n");51 else printf("YES\n");52 } 53 return 0;54 }
3.（HDOJ1247）http://acm.hdu.edu.cn/showproblem.php?pid=1247
题意：给定若干个字符串，找出这样的字符串——它可由其他两个字符串拼接得到。
法1：
分析：先将所有单词存入字典树中，然后对每个单词枚举可以分成的两部分形式（用cstring中的函数strncpy）进行判断这两部分是否都存在于树中
介绍：strncpy()：strncpy(dest,src,n); strncpy把src所指向以'\0'结尾的字符串的前n个字符复制到dest所指的数组中，返回指向dest的指针。
当n>=sizeof(src)时，拷贝正确，并在dest字符串后面加入'\0';
当n<sizeof(src)时，只拷贝src前n-1个字符串到dest，不会为dest字符串后面加入'\0';
注意：可能存在hat hathat这样的情况即一个单词用两次拼成另一个单词；单词长度未知，数组尽量开大;对于存两部分的数组初始化为"\0"这样的形式
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn=200010; 6 int ch[maxn][27]; 7 bool val[maxn]; 8 int sz; 9 char s[maxn][105];10 11 12 void init()13 {14 sz=0;15 memset(ch,0,sizeof(ch));16 memset(val,false,sizeof(val));17 }18 19 void insert(char *s)20 {21 int u=0,c;22 for ( int i=0;s[i];i++ )23 {24 c=s[i]-'a';25 if ( !ch[u][c] ) ch[u][c]=++sz;26 u=ch[u][c];27 }28 val[u]=true;29 }30 31 bool query(char *s)32 {33 int u=0,c;34 for ( int i=0;s[i];i++ )35 {36 c=s[i]-'a';37 if ( !ch[u][c] ) return false;38 u=ch[u][c];39 }40 return val[u];41 }42 43 int main()44 {45 int cnt=0,n,i,j,k,m,x,y,z,ans,len;46 init();47 while ( scanf("%s",s[++cnt])!=EOF ) insert(s[cnt]);48 for ( i=1;i<=cnt;i++ )49 {50 len=strlen(s[i]);51 char str1[105]="\0";52 char str2[105]="\0";53 for ( j=1;j
不用strnpy分解一个单词（改动模板）
1 #include2 #include 3 using namespace std; 4 int ch[200010][27]; 5 int sz; 6 int val[200010]; 7 char str[50005][20]; 8 void init() 9 {10 sz=0;11 memset(ch,0,sizeof(ch));12 memset(val,0,sizeof(val));13 }14 15 void insert(char* s)16 {17 int u=0,c,i;18 for ( i=0;i