https://vjudge.net/problem/HDU-1671
大意是给出g组每组n个电话号码，判断该组号码是否合法（如91125426和911这两个号码不合法，拨出911会直接接通第二个号码，第一个号码打不过去）
由于从头开始找子串，用 黑科技 字典树。
每输入一个号码，逐位创建子节点，号码结束后设置布尔值标记。
用结构体建树：isend判断是否为单词结尾，next存储指定儿子（0-9）的编号，若没有则记为0。
一个比较暴力的算法：遍历一遍字典树，如果有一个节点是单词的结尾，但next不为空（有儿子），则输出NO。
#include <bits/stdc++.h> using namespace std; struct Node{ bool isend; int next[10]; }; Node trieTree[100010]; int size=1; void Insert(char c[]){ int curr=1; int len=strlen(c); for(int i=0; i<len; i++){ int num = c[i]-‘0‘; if(!trieTree[curr].next[num]) trieTree[curr].next[num] = ++size; curr = trieTree[curr].next[num]; } trieTree[curr].isend = true; return; } void init(){ size=1; memset(trieTree, 0, sizeof(trieTree)); } bool isempty(int a[]){ for(int i=0; i<10; i++){ if(a[i]) return false; } return true; } int main(){ int g; cin >> g; while(g--){ init(); int n; cin >> n; while(n--){ char str[20]; cin >> str; Insert(str); } bool flag = true; for(int i=1; i<=size; i++){ if(trieTree[i].isend && !isempty(trieTree[i].next)) flag = false; } if(flag) cout << "YES\n"; else cout << "NO\n"; } return 0; }
稍微巧妙一点的算法是，在输入过程直接判断，若有节点已被标记为isend（该号码包含了其他号码）或整个输入过程没有创建新的节点（有其他号码包含该号码）则输出NO。
先记一下，回头放思路改良后的代码。
原文：https://www.cnblogs.com/miserweyte/p/11153037.html
