acm/poj2001 at master · zhuangAnjun/acm · GitHub

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
#include<iostream>
#include<string>
using namespace std;
struct trie
{
	int flag;
	trie *node[27];
};
trie *tree ;
void creattree(string s)
{
	int l = s.length();
	trie *p = tree;
	for (int i = 0; i<l; i++)
	{
		if (p->node[s[i] - 'a'] == 0)
		{
			p->node[s[i] - 'a'] = new trie;
			p = p->node[s[i] - 'a'];
			for (int j = 0; j < 27; j++)
			p->node[j] = 0;
			p->flag = 0;
		}
		else
		p = p->node[s[i] - 'a'];

		p->flag++;
	}
}
void print(string s)
{
	string out;
	int l = s.length();
	trie *p = tree;
	for (int i = 0; i<l; i++)
	{
		out += s[i];
		if (p->node[s[i] - 'a']->flag == 1)
		{
			cout << s << ' ' << out << endl;
			return;
		}
		p = p->node[s[i] - 'a'];
	}
	cout << s << ' ' << s << endl;
}
void del(trie *p)
{
	for (int i = 0; i<27; i++)
	{
		if (p->node[i] != 0)
			del(p->node[i]);
	}
	delete p;
}
int main()
{
	string s[1002];
	int i = 0;
	tree = new trie;
	for (int j = 0; j < 27; j++)
		tree->node[j] = 0;
	while (cin >> s[i])
	{
		creattree(s[i]);
		i++;
	}
	for (int j = 0; j<i; j++)
	{
		print(s[j]);
	}
		 del(tree);
}