1471：【例题1】Phone List
时间限制: 1000 ms 内存限制: 65536 KB 提交数: 1777 通过数: 609 【题目描述】 原题来自：POJ 3630
给定 n 个长度不超过 10 的数字串，问其中是否存在两个数字串 S,T，使得 S 是 T 的前缀，多组数据。
【输入】 第一行一个整数 T，表示数据组数。
对于每组数据，第一行一个数 n，接下来 n 行输入 n 个数字串。
【输出】 对于每组数据，若存在两个数字串 S，T，使得 S 是 T 的前缀，则输出 NO ，否则输出 YES 。
请注意此处结果与输出的对应关系！
【输入样例】 2 3 911 97625999 91125426 5 113 12340 123440 12345 98346 【输出样例】 NO YES 【提示】 数据范围：
对于 100% 的数据，1≤T≤40,1≤n≤104 。
思路分析：题目大概意思就是判断一个号码是不是其他号码的前缀。直接上字典树。字典树就是给前缀数目统计，并且给号码进行标记。如果一个前缀次数 >= 2次同时这个前缀是一个号码，那么输出NO，否则输出YES。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int N = 1e5+5; int T,n,cnt,flag,f; string s; int tree[N][26]; int tail[N]; int insert(){ int len = s.size(),now=0; for(int i = 0; i < len; i++) { int x = s[i]-'0'; if(tree[now][x] == 0) { tree[now][x] = ++cnt;//创建一个新节点，并把这条边给记录 f = 1; } now = tree[now][x]; if(tail[now]) flag = 1; } tail[now] = 1; return flag == 1 || f == 0; } int main(){ cin >> T; while(T--){ memset(tree,0,sizeof(tree)); memset(tail,0,sizeof(tail)); cnt = 0; int res = 0; cin >> n; while(n--) { flag = f= 0; cin >>s; if(insert()) res = 1; } printf("%s\n",res==1?"NO":"YES"); } return 0; }