POJ2001 字典树

这题在 cnt 变量这里卡了好久，一直 WA 着，才发觉不对。、

和常规的题思路一致，查询的时候找到第一个 cnt 为 1 的结点就是解，注意 insert 函数 cnt 的更新必须更新 next 指针，root 单独更新，如果要到此结点了更新 cnt，那么最后的一个结点要更新 cnt，如果不更新会发生错误。

我的代码，加上了注释：

#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];
  int cnt;
} node[MAX], *root;
int K;

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

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

void insert(char* s) {
  Node* ptr = root;
  char* p = s;
  int id;
  ptr->cnt++;
  // here we update the cnt at first when we reach it.
  while (*p) {
    id = *(p++) - 'a';
    if (ptr->ne[id] == NULL) {
      ptr->ne[id] = New();
    }
    ptr = ptr->ne[id];
    ptr->cnt++;
  }
}

char* find(char* s) {
  char* p = s;
  static char ret[30];
  int top = 0;
  Node* ptr = root;
  int id;
  while (*p) {
    if (ptr->cnt == 1) {
      ret[top] = 0;
      return ret;
    }
    ret[top++] = *p;
    id = *(p++) - 'a';
    ptr = ptr->ne[id];
  }
  return s;
}

char s[1100][30];

int main() {
  int n = 0;
  init();
  while (gets(s[n])) {
    insert(s[n++]);
  }
  for (int i = 0; i < n; i++) {
    printf("%s %s\n", s[i], find(s[i]));
  }
  return 0;
}