#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define tt tuple<int,int,int>
#define NMAX 100005
#define MOD 1000000007
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
struct node {
map<int, int> next;
int id;
bool marc;
node(){
id = -1;
next.clear();
marc = 0;
}
};
vector<node> tri = {node()};
string resp;
int new_node() {
tri.push_back(node());
return tri.size()-1;
}
void insere(string &s, int i) {
int k = 0;
for(auto c : s) {
if(!tri[k].next.count(c)) {
tri[k].next[c] = new_node();
}
k = tri[k].next[c];
}
tri[k].id = i;
}
void DFS(int x) {
if(tri[x].id != -1)
resp.push_back('P');
char c;
int y = 0;
for(auto [d, it] : tri[x].next) {
if(tri[it].marc) {
y = it;
c = d;
continue;
}
resp.push_back(d);
DFS(it);
resp.push_back('-');
}
if(y) {
resp.push_back(c);
DFS(y);
}
}
int32_t main() { faster
int n;
cin>>n;
string mx;
for(int i = 1; i <= n; i++) {
string s;
cin>>s;
insere(s, i);
if(s.size() > mx.size()) {
mx = s;
}
}
int k = 0;
for(auto c : mx) {
k = tri[k].next[c];
tri[k].marc = 1;
}
DFS(0);
cout<<resp.size()<<"\n";
for(auto c : resp)
cout<<c<<"\n";
}
# | 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... |