# Phone List

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 235 Accepted Submission(s): 92

Problem Description
Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:
1. Emergency 911
2. Alice 97 625 999
3. Bob 91 12 54 26
In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.

Input
The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output
For each test case, output “YES” if the list is consistent, or “NO” otherwise.

Sample Input
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output
NO
YES

Source
2008 “Insigma International Cup” Zhejiang Collegiate Programming Contest – Warm Up（3）

Recommend
lcy

这道题，属于Trie的入门级别的题目。但是在这里先介绍1下不用Trie怎样解决这道题。在1堆号码中,

strncmp(): 这个函数用来比较s1和s2字符串，这个函数将返回1个值， 它的符号与第1对不同的字符的比较结果相干。如果两个字符串相等的话，strncmp将返回0。如果s1是s2的1个子串的话，s1小于s2。另外还有，函数 int strncmp (const char *s1, const char *s2, size_t size) 此函数与strcmp极其类似。不同的地方是，strncmp函数是指定比较size个字符。也就是说，如果字符串s1与s2的前size个字符相同，函数返回值为0。

/*
* c.cpp
*
* Created on: 2015年3月7日
*/

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 10001;

char num_str[maxn][11];//用于存储号码字符串

/**
* 让号码字符串按字典序升序排列
*/
int cmp(const void* a,const void* b){
return strcmp((char*)a,(char*)b);
}

int main(){
int t;
scanf("%d",&t);
while(t–){
int n;
scanf("%d",&n);

int i;
for(i = 0 ; i < n ; ++i){//顺次读入n个号码
scanf("%s",num_str[i]);
}

qsort(num_str,n,sizeof(num_str[0]),cmp);//将n个号码按字典序排列

bool flag = false;//用于标记是不是有号码是其他号码的前缀
for(i = 0 ; i < n⑴ ; ++i){//遍历所有的号码字符串
//如果有号码的前n个字符与其他号码的前n个字符是1样的.
if(strncmp(num_str[i],num_str[i+1],strlen(num_str[i] )) == 0){
flag = true;//.则表明该号码是另外1个号码的前缀
break;//跳出循环
}
}

if(flag == true){//如果由号码是其它号码的前缀
printf("NO
");//打印NO
}else{//如果没有号码是其它号码的前缀
printf("YES
");//打印YES
}
}

return 0;
}

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！