Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给出n个字符串的表，问每个字符串的简化表示。简化表示的要求是，以该字符串的最短的而且不能产生歧义的前缀来表示。
思路：字典树，多一个cnt属性，每次insert的时候，路过的每个节点的cnt++
find的时候从root往下扫。。遇到的cnt为1的节点结尾的字符串。。就是该单词的唯一表示。。。
按照这个思路写了一发。。。1A好开心哈哈哈
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月16日 星期二 02时55分22秒
4File Name :code/poj/2001.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <stack>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <deque>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E3+7;
34char s[N][25];
35int n;
36struct Trie
37{
38 struct Node
39 {
40 Node *nxt[26];
41 int cnt;
42 Node()
43 {
44 for ( int i = 0 ; i < 26; i++) nxt[i] = NULL;
45 cnt = 0 ;
46 }
47 };
48 Node *root;
49 void init()
50 {
51 root = new Node();
52 }
53 Trie()
54 {
55 root = new Node();
56 }
57 void Insert(char *s)
58 {
59 Node *u = root;
60 int len = strlen(s);
61 for ( int i = 0 ; i < len ; i++)
62 {
63 int v = s[i]-'a';
64 if (u->nxt[v]==NULL) u->nxt[v] = new Node();
65 u = u->nxt[v];
66 u->cnt++;
67 }
68 }
69 string Find(char *s)
70 {
71 Node *u = root;
72 string res="";
73 int len = strlen(s);
74 for ( int i = 0 ; i < len ; i++)
75 {
76 int v = s[i]-'a';
77 res = res + s[i];
78 u = u->nxt[v];
79 if (u->cnt==1) return res; //cnt为1表示应该就唯一了吧。。。
80 }
81 }
82}trie;
83int main()
84{
85 #ifndef ONLINE_JUDGE
86 freopen("code/in.txt","r",stdin);
87 #endif
88 n = 0 ;
89 trie.init();
90 while (~scanf("%s",s[n++]));
91 n--;
92 for ( int i = 0 ; i <n ; i++)
93 {
94 //cout<<"i:"<<i<<" s[i]:"<<s[i]<<endl;
95 trie.Insert(s[i]);
96 }
97 for ( int i = 0 ; i < n ; i++)
98 {
99 string ans = trie.Find(s[i]);
100 cout<<s[i]<<" "<<ans<<endl;
101 }
102 #ifndef ONLINE_JUDGE
103 fclose(stdin);
104 #endif
105 return 0;
106}