#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#ifdef LOCAL
#include <algo/debug.h>
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long;
const int N = 500005;
string ch;
struct Trie
{
struct Node
{
int child[26], h, mx;
int exist, cnt;
} nodes[N];
vector<char> ans;
int cur;
Trie() : cur(0)
{
memset(nodes[0].child, -1, sizeof nodes[0].child);
nodes[0].exist = nodes[0].cnt = 0;
}
int new_node()
{
cur++;
memset(nodes[cur].child, -1, sizeof nodes[cur].child);
nodes[cur].exist = nodes[cur].cnt = 0;
return cur;
}
void add(string s)
{
int pos = 0;
for (char x : s)
{
int c = x - 'a';
if (nodes[pos].child[c] == -1)
nodes[pos].child[c] = new_node();
int npos = nodes[pos].child[c];
nodes[npos].h = nodes[pos].h + 1;
pos = npos;
nodes[pos].cnt++;
}
nodes[pos].exist++;
}
void dfs(int pos)
{
for (int i = 1; i <= nodes[pos].exist; ++i)
ans.eb('P');
for (int c = 0; c < 26; ++c)
{
if (c == nodes[pos].mx)
continue;
if (nodes[pos].child[c] == -1)
continue;
ans.eb(char(c + 'a'));
dfs(nodes[pos].child[c]);
ans.eb('-');
}
int c = nodes[pos].mx;
if (c == -1)
return;
ans.eb(char(c + 'a'));
dfs(nodes[pos].child[c]);
ans.eb('-');
}
int dfs2(int pos)
{
int mx = 0, k = -1;
for (int c = 0; c < 26; ++c)
{
if (nodes[pos].child[c] == -1)
continue;
int t = dfs2(nodes[pos].child[c]);
if (t > mx)
mx = t, k = c;
}
nodes[pos].mx = k;
return max(mx, nodes[pos].h);
}
};
Trie trie;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int n, mx = 1;
string s, cur = "";
cin >> n;
vector<char> v;
for (int i = 1; i <= n; ++i)
{
cin >> s;
trie.add(s);
if (mx < s.size())
mx = s.size(), ch = s;
}
trie.dfs2(0);
trie.dfs(0);
vector<char> ans = trie.ans;
while (ans.back() == '-')
ans.pop_back();
cout << ans.size() << '\n';
for (char x : ans)
cout << x << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |