// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
vector<char> ans;
string a;
struct Prefix_Trie
{
int n;
struct node {
int exist = 0;
int disttoleaf = 1;
int lovchi = 0;
array<int, 26> child;
};
vector<node> tree;
int id = 0;
Prefix_Trie(){
tree.push_back(node());
}
int newnode(){
id++;
tree.push_back(node());
return id;
}
void insert(string & a){
int pos = 0;
for(auto &elm: a){
int val = elm - 'a';
if(!tree[pos].child[val])tree[pos].child[val] = newnode();
pos = tree[pos].child[val];
}
tree[pos].exist++;
}
void distcompute(int pos){
for(int i=0; i<26; ++i){
if(!tree[pos].child[i])continue;
distcompute(tree[pos].child[i]);
int nxt = tree[pos].child[i];
if(tree[nxt].disttoleaf + 1 > tree[pos].disttoleaf){
tree[pos].lovchi = nxt;
tree[pos].disttoleaf = tree[nxt].disttoleaf + 1;
}
}
}
void dfs(int pos){
int savesz = a.size();
if(tree[pos].exist){
ans.push_back('P');
}
int j = -1;
for(int i=0; i<26; ++i){
if(!tree[pos].child[i])continue;
int nxt = tree[pos].child[i];
if(nxt == tree[pos].lovchi){
j = i;
continue;
}
a.push_back(char('a' + i));
// cout << a << '\n';
ans.push_back(char('a' + i));
dfs(nxt);
while(a.size() != savesz){
a.pop_back();
ans.push_back('-');
}
}
if(j != -1){
a.push_back(char('a' + j));
ans.push_back(char('a' + j));
dfs(tree[pos].lovchi);
}
}
};
Prefix_Trie trie;
void solve(){
int n;cin >> n;
for(int i=1; i<=n; ++i){
string a;cin >> a;
trie.insert(a);
}
trie.distcompute(0);
trie.dfs(0);
cout << ans.size() << '\n';
for(auto &elm: ans)cout << elm << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
# | 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... |