【题目来源】
https://www.acwing.com/problem/content/163/
【题目描述】
给出一个电话列表，如果列表中存在其中一个号码是另一个号码的前缀这一情况，那么就称这个电话列表是不兼容的。
假设电话列表如下：
Emergency 911
Alice 97625999
Bob 91125426
在此例中，报警电话号码（911）为 Bob 电话号码（91125426）的前缀，所以该列表不兼容。
【输入格式】
第一行输入整数 t，表示测试用例数量。
对于每个测试用例，第一行输入整数 n，表示电话号码数量。
接下来 n 行，每行输入一个电话号码，号码内数字之间无空格，电话号码不超过 10 位。
【输出格式】
对于每个测试用例，如果电话列表兼容，则输出 YES。
否则，输出 NO。
【数据范围】
1≤t≤40,
1≤n≤10000
【输入样例】
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
【输出样例】
NO
YES
【算法分析】
● 大家都有查英文单词的经验。例如查单词“cat”，需先翻到字典的 c 部分，再依次找到第 2 个字母 a、第 3 个字母 t。一共查找 3 次便可。易知，在字典中查单词，查找次数最多为单词中的字母个数。字典树（Trie 树）就是模拟这个操作的数据结构。
● 字典树（Trie 树）是一种用于快速检索的多叉树结构。在检索过程中，充分利用字符串的公共前缀降低查询的时间开销，最大限度地减少无谓的字符串比较，从而达到快速检索的目的。
● 除根结点外，字典树的每个结点只包含一个字符。
● 字典树中每个结点都有一个序号。字典树的根结点为空结点，序号为 0。
从代码层面来讲，本例中的 sn[p][u] 表示序号为 p 的结点的子结点的序号。cnt[p] 表示以序号为 p 的结点结尾的字符串个数。由于本例规定“电话号码不超过 10 位”，故任意结点最多有 10 个分支，进而可以理解代码 sn[p][u] 中的 u 为由字符 '0'~'9' 分别减去 '0' 而得的 0~9。
● 本例中的 insert() 函数与 https://blog.csdn.net/hnjzsyjyj/article/details/138599488 中的完全一致，而 query() 函数有差异。
这是因为本例是要找其中一个号码是另一个号码的前缀，所以只要找到任何一个前缀的时候，就要返回 1。即：if(cnt[p]) return 1;
特别的，若样例中存在两个或多个一样的字符串，即 cnt[p]>=2，就要返回 1。
● 字典树在实现时，会对每个字符串的结尾设置标记。
字符串“big、do、dog、dob、date、fat”的字典树（Trie 树）如下所示：
图中绿底儿的结点，表示字符串的末尾。
● 字典树常用于词频统计、前缀匹配、字符串检索、字符串排序等。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
string str[maxn];
int sn[maxn][10]; //sn[p][u] indicates the serial number
int cnt[maxn]; //number of words ending in the current node
int idx;void insert(string s) {int p=0; //root=0for(int i=0; i<s.size(); i++) {int u=s[i]-'0';if(!sn[p][u]) sn[p][u]=++idx;p=sn[p][u];}cnt[p]++;
}int query(string s) {int p=0; //root=0for(int i=0; i<s.size(); i++) {int u=s[i]-'0';if(cnt[p]) return 1;p=sn[p][u];}if(cnt[p]>=2) return 1;return 0;
}int n;
int main() {int T;cin>>T;while(T--) {idx=0;memset(sn,0,sizeof(sn));memset(cnt,0,sizeof(cnt));cin>>n;bool flag=true;for(int i=1; i<=n; i++) {cin>>str[i];insert(str[i]);}for(int i=1; i<=n; i++) {if(query(str[i])) {flag=false;break;}}if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}/*
in:
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346out:
NO
YES
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/138599488
https://www.acwing.com/solution/content/72199/
