Advertisement
Guest User

Untitled

a guest
Jan 24th, 2020
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.97 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <map>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. map <vector <int>, pair <vector <int>, int>> dfs_list;
  9. map <vector <int>, int> numb;
  10. vector <int> o(26);
  11. pair <vector<int>, int> o1(o, 1);
  12.  
  13. pair <vector <int>, int> dfs( vector <int> a )
  14. {
  15. if( dfs_list[a].second )
  16. return dfs_list[a];
  17. else
  18. {
  19. int s = 0;
  20. int i;
  21. for( i = 0; i < 26; i++ )
  22. s+=a[i];
  23. if( s == 1 )
  24. dfs_list[a] = o1;
  25. else
  26. {
  27. s = 0;
  28. vector <int> u(26);
  29. map <int, vector <int>> mas;
  30. for( i = 0; i < 26; i++ )
  31. if( a[i] )
  32. {
  33. u = a;
  34. u[i]--;
  35. if( numb[u] )
  36. {
  37. mas[s] = u;
  38. s++;
  39. }
  40. }
  41. if( !s )
  42. dfs_list[a] = o1;
  43. else
  44. {
  45. int k = 0;
  46. int ways[s];
  47. for( i = 0; i < s; i++ )
  48. ways[i] = dfs( mas[i] ).second;
  49. int l = ways[0];
  50. for( i = 1; i < s; i++ )
  51. if( ways[i] > l )
  52. {
  53. l = ways[i];
  54. k = i;
  55. }
  56. dfs_list[a] = make_pair(mas[k], ways[k]+1);
  57. }
  58. }
  59. return dfs_list[a];
  60. }
  61. }
  62.  
  63. int main()
  64. {
  65. cin.tie(0);
  66. ios_base::sync_with_stdio(0);
  67. int n;
  68. cin >> n;
  69. vector<string> plate_words(n);
  70. vector<vector<int>> plate_vectors(n);
  71. int k;
  72. int i;
  73. for( k = 0; k < n; k++ )
  74. {
  75. cin >> plate_words[k];
  76. plate_vectors[k].resize(26);
  77. for( i = 0; i < plate_words[k].length(); i++ )
  78. plate_vectors[k][plate_words[k][i]-'a']++;
  79. }
  80. int m;
  81. cin >> m;
  82. vector<string> dict_words(m);
  83. vector<vector<int>> dict_vectors(m);
  84. for( k = 0; k < m; k++ )
  85. {
  86. cin >> dict_words[k];
  87. dict_vectors[k].resize(26);
  88. for( i = 0; i < dict_words[k].length(); i++ )
  89. dict_vectors[k][dict_words[k][i]-'a']++;
  90. numb[dict_vectors[k]] = k + 1;
  91. }
  92. for( k = 0; k < n; k++ )
  93. {
  94. int f = 0;
  95. int d = dfs_list[plate_vectors[k]].second;
  96. cout << d << "/n";
  97. vector<int> v = plate_vectors[k];
  98. string s = plate_words[k];
  99. i=k;
  100. while( v != o )
  101. {
  102. cout << s <<" -> ";
  103. v = dfs_list[v].first;
  104. i = numb[v] - 1;
  105. s = plate_words[i];
  106. f++;
  107. }
  108. if( f == dict_words[k].length() )
  109. cout << "./n";
  110. }
  111.  
  112. return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement