山东第一届省赛1001 Phone Number（字典树）

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大学生程序设计竞赛

题意：给出几个字符串问是否会有前缀产生，直接字典树搞定

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 const int Max = 1000 + 10;
 7 struct Node
 8 {
 9     int value;
10     int cnt;
11     Node * Next[10];
12 };
13 Node * root;
14 char str[Max];
15 bool build(char * s)
16 {
17     Node * p = root, *temp;
18     int len = strlen(s);
19     for (int i = 0; i < len; i++)
20     {
21         int id = str[i] - '0';
22         if (p->Next[id] == NULL)
23         {
24             temp = new Node;
25             temp->value = id;
26             temp->cnt = 0;
27             for (int i = 0; i < 10; i++)
28                 temp->Next[i] = NULL;
29             p->Next[id] = temp;
30         }
31         p = p->Next[id];
32         if (p->cnt)
33             return false;
34     }
35     return true;
36 }
37 void destroy(Node * temp)
38 {
39     if (temp == NULL)
40         return;
41     for (int i = 0; i < 10; i++)
42         destroy(temp->Next[i]);
43     delete temp;
44 }
45 int main()
46 {
47     int n;
48     while (scanf("%d", &n) != EOF && n)
49     {
50         root = new Node;
51         for (int i = 0; i < 10; i++)
52             root->Next[i] = NULL;
53         bool flag = true;
54         while (n--)
55         {
56             scanf("%s", str);
57             if (!flag)
58                 continue;
59             if (!build(str))
60                 flag = false;
61         }
62         if (flag)
63             printf("YES
");
64         else
65             printf("NO
");
66         destroy(root);
67     }
68     return 0;
69 }

View Code