HDU1671 字典树

发表于 分类于

这题纠结了好久，之前没有考虑到 flag 标记，如果有如下的数据，之前的想法就错了:

1
2
3
4
1
2
00000
000

直接建字典树，注意一下几点：

  1. 如果当前的结点是标记了 danger 的，那么就直接返回 false，表示有前缀。
  2. 如果遍历到最后依然没有发现 danger 标记，要考虑这个结点有没有后继，如果有，说明他是某些结点的前缀，这个用 flag 标记。

自己在代码里加了一些注释，以便理解。

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;
const int MAX = 1000000;

struct Node {
  Node* ne[10];
  bool danger, flag;  // if node has next pointer set the flag true
} node[MAX], *root;
int K;

Node* New() {  // get a new pointer which has not be allocate.
  Node* ret = &node[K++];
  for (int i = 0; i < 10; i++) {
    ret->ne[i] = NULL;
  }
  ret->danger = false;
  ret->flag = false;
  return ret;
}

void init() {
  K = 0;
  root = New();
}

bool insert(char* s) {
  Node* ptr = root;
  char* p = s;
  int id;

  // go along the tree and find whether
  // s has a dangerous prefix.
  while (*p) {
    id = *(p++) - '0';
    if (ptr->danger) {
      return false;
    }
    if (ptr->ne[id] == NULL) {
      ptr->ne[id] = New();
    }
    ptr->flag = true;
    // set the flag true because this node has next pointer.
    ptr = ptr->ne[id];
  }
  ptr->danger = true;

  // notice: if the next pointer is not null
  // we say s is a prefix of some words.
  if (ptr->flag) {
    return false;
  }
  return true;
}

int main() {
  int t;
  int n;
  bool done;
  char s[1100];
  scanf("%d", &t);
  while (t--) {
    init();
    scanf("%d", &n);
    done = true;
    for (int i = 0; i < n; i++) {
      scanf("%s", s);
      if (done) {
        done = insert(s);
      }
    }
    if (done) {
      puts("YES");
    } else {
      puts("NO");
    }
  }
  return 0;
}