#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int maxn = 25000 * 20 + 5;
int cnt = 0, nex[maxn][26], n; string mx = ""; vector<string> vs;
vector<bool> flag(maxn, false), bac(maxn, false); vector<char> ans;
void ins(string& s, bool f) {
int p = 0;
for (int i = 0; i < s.length(); i++) {
int c = s[i] - 'a';
if (!nex[p][c]) nex[p][c] = ++cnt;
p = nex[p][c];
flag[p] = f;
if (i == s.length() - 1) bac[p] = true;
}
}
void dfs(int u) {
if (bac[u]) ans.pb('P');
if (flag[u]) {
for (int i = 0; i < 26; i++) if (!flag[nex[u][i]] && nex[u][i]) ans.pb((char) (i + 'a')), dfs(nex[u][i]), ans.pb('-');
for (int i = 0; i < 26; i++) if (flag[nex[u][i]] && nex[u][i]) ans.pb((char) (i + 'a')), dfs(nex[u][i]), ans.pb('-');
} else {
for (int i = 0; i < 26; i++) if (nex[u][i]) ans.pb((char) (i + 'a')), dfs(nex[u][i]), ans.pb('-');
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
while (n--) {
string s; cin >> s; vs.pb(s);
if (s.length() > mx.length() || (s.length() == mx.length() && s > mx)) mx = s;
}
for (auto& s : vs) if (s != mx) ins(s, false);
ins(mx, true);
flag[0] = true;
dfs(0);
while (ans.back() == '-') ans.pop_back();
cout << ans.size() << "\n";
for (char c : ans) cout << c << "\n";
return 0;
}
Compilation message
printer.cpp: In function 'void ins(std::string&, bool)':
printer.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | for (int i = 0; i < s.length(); i++) {
| ~~^~~~~~~~~~~~
printer.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | if (i == s.length() - 1) bac[p] = true;
| ~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1236 KB |
Output is correct |
2 |
Correct |
2 ms |
1364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3284 KB |
Output is correct |
2 |
Correct |
11 ms |
6608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
7836 KB |
Output is correct |
2 |
Correct |
7 ms |
2316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
18828 KB |
Output is correct |
2 |
Correct |
76 ms |
41536 KB |
Output is correct |
3 |
Correct |
44 ms |
22576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
15160 KB |
Output is correct |
2 |
Correct |
87 ms |
49340 KB |
Output is correct |
3 |
Correct |
48 ms |
25532 KB |
Output is correct |
4 |
Correct |
80 ms |
46736 KB |
Output is correct |