#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, mxval;
TrieNode() {
memset(child, 0, sizeof child);
Cnt = End = mxval = 0;
}
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++;
mxval = s.size();
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(), mxval = max(mxval, child[i]->mxval);
}
}
void Dfs() {
set<pair<int, int>> st;
for (int i = 0; i < 26; i++)
if (child[i])
st.insert({child[i]->mxval, 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:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | 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);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Line "h j x g q k P - - - - - - i u ... l m w f i r l g b d e v j d P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Line "q g j P - - - t d s P - - - l ... 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Line "w u y P - - - j P c h g P - - ... - - e y n o r w r b i z a i P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1884 KB |
Line "v P i z f r P - - - - l s c b ... 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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
6488 KB |
Line "a P e u g h i h q i y P - - - ... n i c j t u k m w m l d d z P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
15824 KB |
Line "a P y m P - n d P - - r c P - ... k w z a k q u b h s t c d q P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
39308 KB |
Line "a P l P s k P - - n l m P - - ... h i h q z w z o m l n c z u P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
30668 KB |
Line "a P a P p e w P - - - g l e P ... P - - - j t e a r n h d j e P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
