sdutoj 2151 Phone Number

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2151

Phone Number

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

We know that if a phone number A is another phone number B’s prefix, B is not able to be called. For an example, A is 123 while B is 12345, after pressing 123, we call A, and not able to call B.
Given N phone numbers, your task is to find whether there exits two numbers A and B that A is B’s prefix.

输入

The input consists of several test cases.
The first line of input in each test case contains one integer N (0<N<1001), represent the number of phone numbers.
The next line contains N integers, describing the phone numbers.
The last case is followed by a line containing one zero.

输出

For each test case, if there exits a phone number that cannot be called, print “NO”, otherwise print “YES” instead.

示例输入

示例输出

NO
YES

提示

来源

2010年山东省第一届ACM大学生程序设计竞赛

示例程序

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 
 7 struct node
 8 {
 9     int count;
10     node *child[10];
11     node()
12     {
13         count=0;
14         int i;
15         for(i=0; i<10; i++)
16             child[i]=0;
17     }
18 };
19 
20 node *current, *newnode;
21 
22 void insert(node *root, char *ss)
23 {
24     //printf("%s*****
",ss);
25     int i, m;
26     current=root;
27     for(i=0; i<strlen(ss); i++)
28     {
29         m=ss[i]-'0';
30         if(current->child[m]!=NULL)
31         {
32             current=current->child[m];
33             ++(current->count);
34         }
35         else
36         {
37             newnode=new node;
38             ++(newnode->count);
39             current->child[m]=newnode;
40             current=newnode;
41         }
42     }
43 }
44 
45 int search(node *root, char *ss)
46 {
47     //printf("%s*****
",ss);
48     int i, m;
49     current=root;
50     for(i=0; i<strlen(ss); i++)
51     {
52         m=ss[i]-'0';
53         if(current->child[m]==NULL)
54             return 0;
55         current=current->child[m];
56     }
57     return current->count;
58 }
59 
60 int main()
61 {
62     char str[30], s[1010][30];
63     int t, flag, i;
64     while(scanf("%d",&t))
65     {
66         if(t==0) break;
67         flag=0;
68         node *root=new node;
69         for(i=0; i<t; i++)
70         {
71             scanf("%s",str);
72             strcpy(s[i], str);
73             //puts(s[i]);
74             insert(root, str);
75         }
76         for(i=0; i<t; i++)
77         {
78             if(search(root, s[i])-1)
79             {
80                 flag=1;
81                 break;
82             }
83         }
84         if(flag==0) printf("YES
");
85         else printf("NO
");
86     }
87     return 0;
88 }

View Code