poj 2001 Shortest Prefixes ——字典树入门

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

char a[1000+10][25];
const int sonnum = 26, base = 'a';

struct Trie 
{
  int num; 
  bool terminal;
  struct Trie *son[sonnum];
};

Trie *NewTrie()
{
  Trie *temp = new Trie;
  temp->num = 1; temp->terminal = false;
  for (int i = 0; i < sonnum; ++i) temp->son[i] = NULL;
  return temp;
}

void Insert(Trie *pnt, char *s, int len)
{
  Trie *temp = pnt;
  for (int i = 0; i < len; ++i)
  {
    if (temp->son[s[i]-base] == NULL)
      temp->son[s[i]-base] = NewTrie();
    else temp->son[s[i]-base]->num++;
    temp = temp->son[s[i]-base];
  }
  temp->terminal = true;
}
Trie *Find(Trie *pnt, char *s, int len)
{
  Trie *temp = pnt;
  for (int i = 0; i < len; ++i)
  {
    if (temp->son[s[i]-base]->num == 1)
    {
      printf("%c", s[i]);
      return temp;
    }
    printf("%c", s[i]);
    temp = temp->son[s[i]-base];
  }
  return temp;
}

int main(void)
{
#ifndef ONLINE_JUDGE
  freopen("poj2001.in", "r", stdin);
#endif
  int cnt = 0;
  Trie *tree = NewTrie();
  while (~scanf("%s", a[cnt]))
  {
    Insert(tree, a[cnt], strlen(a[cnt]));
    cnt++;
  }
  for (int i = 0; i < cnt; ++i) 
  {
    printf("%s ", a[i]);
    Find(tree, a[i], strlen(a[i]));
    printf("\n");
  }

  return 0;
}

先建树，再查找，一边查找一遍输出即可。