fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
  6. #define          FORE(i, v)  for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
  7. #define          file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
  8.  
  9. struct Node {
  10. 	Node *child[26];
  11. 	int terminal;
  12. 	Node() {
  13. 		REP(i, 26) child[i] = nullptr;
  14. 		terminal = 0;
  15. 	}
  16. };
  17.  
  18. int N;
  19. string maxS;
  20. Node *root = new Node();
  21.  
  22. void addString(const string &s) {
  23. 	Node *p = root;
  24. 	FORE(it, s) {
  25. 		if (p->child[*it - 'a'] == nullptr) p->child[*it - 'a'] = new Node();
  26. 		p = p->child[*it - 'a'];
  27. 	}
  28. 	p->terminal++;
  29. }
  30.  
  31. void init(void) {
  32. 	cin >> N;
  33. 	REP(i, N) {
  34. 		string s; cin >> s;
  35. 		if (maxS.size() < s.size()) maxS = s;
  36. 		addString(s);
  37. 	}
  38. }
  39.  
  40. string res;
  41.  
  42. void dfs(Node *p, int depth, bool type) {
  43. 	REP(i, p->terminal) res += 'P';
  44. 	if (depth == maxS.size()) return;
  45. 	if (type) {
  46. 		REP(i, 26) if (p->child[i] != nullptr && i != maxS[depth] - 'a') {
  47. 			res += char(i + 'a');
  48. 			dfs(p->child[i], depth + 1, 0);
  49. 			res += '-';
  50. 		}
  51. 		res += maxS[depth];
  52. 		dfs(p->child[maxS[depth] - 'a'], depth + 1, 1);
  53. 	} else {
  54. 		REP(i, 26) if (p->child[i] != nullptr) {
  55. 			res += char(i + 'a');
  56. 			dfs(p->child[i], depth + 1, 0);
  57. 			res += '-';
  58. 		}
  59. 	}
  60. }
  61.  
  62. void process(void) {
  63. 	dfs(root, 0, 1);
  64. 	cout << res.size() << '\n' << res;
  65. }
  66.  
  67. int main(void) {
  68. 	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
  69. 	file("type-printer");
  70. 	init();
  71. 	process();
  72. 	return (0^0);
  73. }
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
3
xycj
xycr
xycrg
stdout
copy 
10
xycjP-rPgP
https://ideone.com/rlQAim
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!