#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;
}
bool flag;
string mx = "";
vector<char> Ans;
const int CHAR = 26;
struct TrieNode {
TrieNode *child[CHAR];
int Cnt, End, mnlen;
TrieNode() {
memset(child, 0, sizeof child);
Cnt = End = 0;
mnlen = 50;
}
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++;
child[cur]->mnlen = 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 DfsMin() {
for (int i = 0; i < 26; i++) {
if (child[i])
child[i]->DfsMin(), mnlen = min(mnlen, child[i]->mnlen);
}
}
void Dfs() {
set<pair<int, int>> st;
for (int i = 0; i < 26; i++)
if (child[i])
st.insert({child[i]->mnlen, 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;
if (s.size() > mx.size())mx = s;
Root->add(s);
}
Root->DfsMin();
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:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | if (i == s.size() - 1) {
| ~~^~~~~~~~~~~~~~~
printer.cpp: In member function 'void TrieNode::erase(int, std::string&)':
printer.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | if (i == s.size() - 1) {
| ~~^~~~~~~~~~~~~~~
printer.cpp: In member function 'bool TrieNode::find(int, std::string&)':
printer.cpp:79:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if (i == s.size() - 1) {
| ~~^~~~~~~~~~~~~~~
printer.cpp: In member function 'int TrieNode::CntPrefix(int, std::string&)':
printer.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | 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 |
348 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 |
1 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 "p w P f x l m w f i r l g b d ... j x a v q c m x z b f i e l 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 "x p P - c d y q x x m o m n d ... i c t n a a h h r g l a z o 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 |
348 KB |
Line "b P n q P - - q h h h P - - - ... - - p g v s l f t h l j c t 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 "a P b z o P - - f i l p u r y ... h p c c y u g q v c r l y l 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 |
6628 KB |
Line "a P h P q h z i P - - - - t p ... k e v v q w j g m o y h z k P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
15780 KB |
Line "a P b P s P i j c v f z o v P ... - j o r t c o y c l l l z 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 |
59 ms |
39268 KB |
Line "a P b P a P e P - - m P g c v ... y l d h q z s k n v d j t r P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
30736 KB |
Line "a P a P t n P - g r x P - - - ... - - - - - m l k i y u k m o P " doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
