Advertisement
Guest User

Untitled

a guest
Aug 21st, 2014
250
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <math.h>
  4. #include <vector>
  5. #include <string>
  6. #include <utility>
  7. #include <stdio.h>
  8. #include <queue>
  9. #include <fstream>
  10. #include <functional>
  11. #include <cstdlib>
  12. #include <map>
  13. #include <set>
  14. #include <math.h>
  15. #include <string.h>
  16. #include <stdlib.h>
  17.  
  18. using namespace std;
  19.  
  20. typedef pair<int, int> ii ;
  21. typedef vector< ii > vii ;
  22. typedef vector<int> vi ;
  23. typedef vector<vi> vvi;
  24. typedef pair< int, string > is;
  25.  
  26. #define pb push_back
  27. #define MAX_N 2000005
  28.  
  29. int n, printable[MAX_N];
  30. int last[MAX_N];
  31. vector< ii > g[MAX_N];
  32. string sol,maxim;
  33. vector< string > sorted;
  34.  
  35. bool cmp(const string &a, const string &b ){
  36. return a.length()>b.length();
  37. }
  38.  
  39. void dfs(int n){
  40.  
  41. for(int i=0;i<g[n].size();i++){
  42. if(!last[g[n][i].first]){
  43. sol.pb(char(g[n][i].second+'a'));
  44. dfs(g[n][i].first);
  45. }
  46. }
  47. for(int i=0;i<g[n].size();i++){
  48. if(last[g[n][i].first]){
  49. sol.pb(char(g[n][i].second+'a'));
  50. dfs(g[n][i].first);
  51. }
  52. }
  53.  
  54. for(int i=0;i<printable[n];i++)
  55. sol.pb('P');
  56.  
  57. sol.pb('-');
  58. }
  59.  
  60. void dfsLast(int n, int pos){
  61. last[n] = 1;
  62. if(pos == maxim.size())
  63. return;
  64. for(int i=0;i<g[n].size();i++){
  65. if(char(g[n][i].second+'a') == maxim[pos] ){
  66. dfsLast(g[n][i].first,pos+1);
  67. break;
  68. }
  69. }
  70. }
  71.  
  72. int main() {
  73.  
  74. #ifdef EVAL
  75. freopen("input.txt", "r", stdin);
  76. freopen("output.txt", "w", stdout);
  77. #endif
  78.  
  79. scanf("%d",&n);
  80. int maxNode = 0;
  81.  
  82. for(int i=0;i<n;i++){
  83. char t[30]; scanf("%s",t);//cin>>t;
  84. string temp = t;
  85. if(temp.length() > maxim.length())
  86. maxim = temp;
  87. sorted.pb(temp);
  88. }
  89.  
  90. //sort(sorted.begin(), sorted.end(), cmp);
  91.  
  92. for(int i=0;i<n;i++){
  93. int nodeCurr = 0;
  94. for(int j=0;j<sorted[i].length();j++){
  95. int ind = -1 ;
  96. for(int k=0;k<g[nodeCurr].size();k++)
  97. if(g[nodeCurr][k].second == sorted[i][j]-'a'){
  98. ind = k;
  99. break;
  100. }
  101. if(ind == -1){
  102. g[nodeCurr].push_back(make_pair(++maxNode, sorted[i][j]-'a'));
  103. ind = g[nodeCurr].size()-1;
  104. }
  105. if(j == sorted[i].length() - 1)
  106. printable[maxNode]++;
  107.  
  108. nodeCurr = g[nodeCurr][ind].first;
  109.  
  110. }
  111. }
  112. /*for(int i=0;i<maxNode;i++){
  113. cout<<i<<": ";
  114. for(int j=0;j<g[i].size();j++)
  115. cout<<g[i][j].first<<" "<<char(g[i][j].second+'a')<<endl;
  116. }*/
  117. dfsLast(0,0);
  118. dfs(0);
  119.  
  120. int k = sol.length()-1;
  121. while(sol[k] == '-')
  122. k--;
  123. printf("%d\n",k+1);
  124. for(int i=0;i<=k;i++)
  125. printf("%c\n",sol[i]);
  126.  
  127. return 0;
  128. }
  129.  
  130. //7 -1 2 -1 5 -2 3 -3 1 1 -1 -2 -1 -3 -4
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement