何为字典树：
如图所示：
每个字符有很多个分支，打黄色标记的就是字符串的结尾，所以这颗字典树中有哪些字符串呢，"ab","ay","ayf","c","cc","cd",其他的枝没有画全。
如何存储：
顺序存储字符串：“ab”“ay”“ayf”“c”“cc”“cd”……(节点编号讲究先到先得)
数组tree[i][j]:代表i节点的第j个儿子的根编号。(获取第几个孩子可以s[i]-‘a‘,以图中5节点举例，就是tree[0][2]=5)
数组flag[i]:为true代表到该节点为一个字符串
https://blog.csdn.net/TDD_Master/article/details/86688586
HDU - 1671 很多电话号码，看有没有一个号码是另一个号码的前缀
思路，看经过的路径上每个点的sum[i]值，如果都大于等于2，说明这个号码是某一个号码的前缀。
#include<cstdio> #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<queue> #include<stack> #include<map> #include<set> #include<cmath> #include<sstream> using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; const int maxn=2e6+5; int tree[maxn][15],sum[maxn],tot=0; char a[10005][15]; int T,n; void add(char *s) { int root=0,id,len=strlen(s); for(int i=0; i<len; ++i) { id=s[i]-‘0‘; if(!tree[root][id]) tree[root][id]=++tot; root=tree[root][id]; sum[root]++; } } bool find(char *s) { int root=0,id,len=strlen(s),tp=0; for(int i=0; i<len; ++i) { id=s[i]-‘0‘; root=tree[root][id]; if(sum[root]>=2) tp++; } if(tp==len) return false; else return true; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0; i<n; ++i) { scanf("%s",a[i]); add(a[i]); } bool pd=0; for(int i=0;i<n;++i){ if(!find(a[i])){ pd=1; break; } } if(!pd) cout<<"YES"<<endl; else cout<<"NO"<<endl; for(int i=0;i<=tot;++i){ for(int j=0;j<10;++j){ tree[i][j]=0; } } } return 0; }
看有没有单词是有其他两个单词合并起来的
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxm = 5e4 + 5; const int maxm2 = 1e6 + 5; char s[maxm][20]; int flag[maxm2], tree[maxm][27]; int tot = 0; void add(char ch[]) { int root = 0, id = 0, len = strlen(ch); for(int i = 0; i < len; i++) { id = ch[i] - ‘a‘; if(!tree[root][id]) tree[root][id] = ++tot; root = tree[root][id]; } flag[root] = 1; } bool find2(char ch[]) { int root = 0, id = 0, len = strlen(ch); for(int i = 0; i < len; i++) { id = ch[i] - ‘a‘; if(!tree[root][id]) return false; root = tree[root][id]; } if(flag[root]) return true; else return false; } bool find1(char ch[]) { int root = 0, id = 0, len = strlen(ch); for(int i = 0; i < len; i++) { id = ch[i] - ‘a‘; if(flag[root] && find2(ch + i)) return true; root = tree[root][id]; } return false; } int main() { int ant = 0; while(~scanf("%s", s[ant])) { // if(s[ant][0] == ‘#‘) break; add(s[ant]); ant++; } for(int i = 0; i < ant; i++) { // printf("%d\n", find1(s[i])); if(find1(s[i])) printf("%s\n", s[i]); } return 0; }
原文：https://www.cnblogs.com/downrainsun/p/10385663.html