Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- #include <cstdlib>
- using namespace std;
- struct vertex {
- int leaf, next[10];
- };
- vertex trie[10000000];
- vertex p;
- int sz = 0;
- int d[9];
- void add (int x) {
- int m = 0;
- while (x > 0) {
- d[m++] = x % 10;
- x /= 10;
- }
- while (m < 9) d[m++] = 0;
- int v = 0;
- for (int i = m - 1; i >= 0; --i) {
- if (trie[v].next[d[i]] == -1) {
- ++sz;
- trie[sz - 1].leaf = 0;
- for (int j = 0; j < 10; ++j) trie[sz - 1].next[j] = -1;
- trie[v].next[d[i]] = sz - 1;
- }
- v = trie[v].next[d[i]];
- }
- ++trie[v].leaf;
- }
- int dfs (int v, int x) {
- if (trie[v].leaf) cout << x << " ";
- for (int i = 0; i < 10; ++i) if (trie[v].next[i] != -1) dfs (trie[v].next[i], x * 10 + i);
- }
- int main () {
- ios_base :: sync_with_stdio (false);
- for (int i = 0; i < 10; ++i) trie[0].next[i] = -1;
- trie[0].leaf = 0;
- sz = 1;
- int n;
- cin >> n;
- for (int i = 0; i < n; ++i) {
- int a;
- cin >> a;
- add (a);
- }
- dfs (0, 0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement