HDU1247 字典树

发表于 分类于

本题思路和一般字典树有所不同，将全部的字符串读入离线处理，insert 操作和大部分字典树一致，接下来就是一个 dfs 函数，枚举全部字符串是否是符合条件的，dfs 的 tim 参数表示了这个是第几次查询，如果遇到 danger 标记，就可以有两种路径，继续本次查询和进入下一个查询，这样讲每一个字符串都判断完毕即可。

我的代码：

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
101
102
103
104
105
106
#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[26];
  bool danger;
} node[MAX], *root;
char in[50010][50];
int K;

Node* New() {
  Node* ret = &node[K++];
  for (int i = 0; i < 26; i++) {
    ret->ne[i] = NULL;
  }
  ret->danger = false;
  return ret;
}

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

void insert(char* s) {
  char* p = s;
  Node* ptr = root;
  int id;
  while (*p) {
    id = *(p++) - 'a';
    if (ptr->ne[id] == NULL) {
      ptr->ne[id] = New();
    }
    ptr = ptr->ne[id];
  }
  ptr->danger = true;
}

bool dfs(char* s, int tim) {
  // tim=0 means that it is the first time search,
  // otherwise it is the second time.
  char* p = s;
  Node* ptr = root;
  int id;
  while (*p) {
    id = *(p++) - 'a';
    if (ptr->ne[id] == NULL) {
      return false;
      // if the next pointer is null, return false.
    }
    ptr = ptr->ne[id];
    // important.
    // if this node is a danger case, we search a second time.
    if (ptr->danger) {
      if (tim == 0 && *p && dfs(p, 1)) {
        return true;
      }
    }
  }
  // if the node is dangerous and the string has been completely search
  // return true.
  if (tim == 1 && ptr->danger) {
    return true;
  } else {
    return false;
  }
}

int main() {
  int n = 0;
  init();
  while (gets(in[n])) {
    insert(in[n]);
    n++;
  }
  for (int i = 0; i < n; i++) {
    if (dfs(in[i], 0)) {
      puts(in[i]);
    }
  }
  return 0;
}