#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
/*-------------------------*/
#define ll long long
#define ld long double
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define Dracarys ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
template<typename T> using indexed_multiset = tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef pair<ll, int> pi;
const int N = 2e5 + 10;
const int infi = 1e9 + 10;
const ll infl = 1e18 + 10;
const int MOD = 1e9 + 7;
const ld eps = 1e-9;
string ScanString() {
char ch[100000];
scanf("%s", ch);
return ch;
}
vector<char> Ans;
const int CHAR = 26;
struct TrieNode {
TrieNode *child[CHAR];
int Cnt, End, val;
TrieNode() {
memset(child, 0, sizeof child);
Cnt = End = 0;
val = 1;
}
void add(int i, string &s) {
int cur = s[i] - 'a';
if (child[cur] == 0) child[cur] = new TrieNode();
child[cur]->Cnt++;
if (i == s.size() - 1) {
child[cur]->End++;
return;
}
child[cur]->add(i + 1, s);
}
void add(string &s) {
add(0, s);
}
void erase(int i, string &s) {
int cur = s[i] - 'a';
child[cur]->Cnt--;
if (i == s.size() - 1) {
child[cur]->End--;
return;
}
child[cur]->erase(i + 1, s);
if (!child[cur]->Cnt) {
delete child[cur];
child[cur] = 0;
}
}
void erase(string &s) {
if (!find(s))return;
erase(0, s);
}
bool find(int i, string &s) {
int cur = s[i] - 'a';
if (child[cur] == 0)return 0;
if (i == s.size() - 1) {
return child[cur]->End > 0;
}
return child[cur]->find(i + 1, s);
}
bool find(string &s) {
return find(0, s);
}
int CntPrefix(int i, string &s) {
int cur = s[i] - 'a';
if (child[cur] == 0)return 0;
if (i == s.size() - 1) {
return child[cur]->Cnt;
}
return child[cur]->CntPrefix(i + 1, s);
}
int CntPrefix(string &s) {
return CntPrefix(0, s);
}
void DfsMax() {
for (int i = 0; i < 26; i++) {
if (child[i])
child[i]->DfsMax(), val += child[i]->val;
}
}
void Dfs() {
set<pair<int, int>> st;
for (int i = 0; i < 26; i++)
if (child[i])
st.insert({child[i]->val, i});
for (auto &it: st) {
Ans.push_back(char('a' + it.second));
if (child[it.second]->End)Ans.push_back('P');
child[it.second]->Dfs();
Ans.push_back('-');
}
}
void clear() {
for (int i = 0; i < CHAR; i++)
if (child[i])
child[i]->clear(), delete child[i], child[i] = 0;
}
};
void RunTime(int Tc) {
int n;
cin >> n;
TrieNode *Root = new TrieNode();
for (int i = 0; i < n; i++) {
string s;
cin >> s;
Root->add(s);
}
Root->DfsMax();
Root->Dfs();
while (Ans.back() == '-')Ans.pop_back();
cout << Ans.size() << endl;
for (auto &it: Ans)cout << it << ' ';
}
int main() {
Dracarys
int T = 1;
//cin >> T;
for (int Tc = 1; Tc <= T; Tc++) {
RunTime(Tc);
}
return 0;
}
Compilation message
printer.cpp: In member function 'void TrieNode::add(int, std::string&)':
printer.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | if (i == s.size() - 1) {
| ~~^~~~~~~~~~~~~~~
printer.cpp: In member function 'void TrieNode::erase(int, std::string&)':
printer.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if (i == s.size() - 1) {
| ~~^~~~~~~~~~~~~~~
printer.cpp: In member function 'bool TrieNode::find(int, std::string&)':
printer.cpp:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if (i == s.size() - 1) {
| ~~^~~~~~~~~~~~~~~
printer.cpp: In member function 'int TrieNode::CntPrefix(int, std::string&)':
printer.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | if (i == s.size() - 1) {
| ~~^~~~~~~~~~~~~~~
printer.cpp: In function 'std::string ScanString()':
printer.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%s", ch);
| ~~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Line "t p t t t y k d u y v x j b z h q u p P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Line "n P - y e r x P - - - - x x v ... y o s s k u g b k i u f f d P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Line "h j x g q k P - - - - - - i u ... - m q p c e a i r h d o n t P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
600 KB |
Line "q g j P - - - t d s P - - - b ... m s g e n n p d l u r n m v P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Line "w u y P - - - r P d x h q n w ... - - - - - - w q v u h w u w P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1884 KB |
Line "u P n P - l o P - - i u z f P ... v i w g d u d c y b a h u w P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
6492 KB |
Line "k P i l P - - n l s P - - - s ... d o o n w l p u i j z m o y P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
21 ms |
15828 KB |
Line "j P w P c P - q j b P - - - m ... - - - - t t p m n k o x o z P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
59 ms |
39116 KB |
Line "s P f P p p i P - - - t j q P ... g z w r w c v r d u l q b a P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
50 ms |
30612 KB |
Line "m P g P o P - y P - g h P - - ... - - - - - n f n z e j d t e P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
