Advertisement
Guest User

Untitled

a guest
Nov 25th, 2015
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5.  
  6. using namespace std;
  7.  
  8. struct let {
  9. int a[26];
  10. };
  11.  
  12. int dp[2050][2050], p[2050][2050], ans[2050][2050], len;
  13. bool amb[2050][2050];
  14. string dict1[10050], t, segm[2050][2050], str;
  15. vector < pair<string, int> > dict2[150];
  16.  
  17. void solve(int l, int r) {
  18. dp[l][r] = 0;
  19. int cnt = 0;
  20. if (r - l + 1 <= 100) {
  21. int lb = -1, rb = (int)dict2[r - l + 1].size() - 1;
  22. while (lb + 1 < rb) {
  23. int mb = (lb + rb) / 2;
  24. if (dict2[r - l + 1][mb].first < segm[l][r])
  25. lb = mb;
  26. else
  27. rb = mb;
  28. }
  29. if (rb >= 0) {
  30. if (dict2[r - l + 1][rb].first == segm[l][r]) {
  31. dp[l][r] = 1;
  32. cnt++;
  33. p[l][r] = r;
  34. ans[l][r] = dict2[r - l + 1][rb].second;
  35. }
  36. if (rb < (int)dict2[r - l + 1].size() - 1 && dict2[r - l + 1][rb + 1].first == segm[l][r])
  37. cnt++;
  38. }
  39. }
  40. for (int i = l; i < r; i++) {
  41. if (dp[l][i] == -1)
  42. solve(l, i);
  43. if (dp[i + 1][r] == -1)
  44. solve(i + 1, r);
  45. if (dp[l][i] == 1 && dp[i + 1][r] > 0) {
  46. if (amb[i + 1][r])
  47. cnt++;
  48. dp[l][r] = dp[l][i] + dp[i + 1][r];
  49. cnt++;
  50. p[l][r] = i;
  51. }
  52. }
  53. if (cnt > 1)
  54. amb[l][r] = true;
  55. }
  56.  
  57. void rec(int l, int r) {
  58. if (p[l][r] == r) {
  59. cout << dict1[ans[l][r]];
  60. if (r != len - 1)
  61. cout << " ";
  62. }
  63. else {
  64. rec(l, p[l][r]);
  65. rec(p[l][r] + 1, r);
  66. }
  67. }
  68.  
  69. bool cmp(pair<string, int> a, pair<string, int> b) {
  70. return a.first < b.first;
  71. }
  72.  
  73. int main()
  74. {
  75. for (int i = 0; i < 2000; i++)
  76. for (int j = 0; j < 2000; j++)
  77. dp[i][j] = -1;
  78. int n;
  79. cin >> str;
  80. len = str.length();
  81. for (int i = 0; i < min(100, len); i++)
  82. for (int j = 0; j < len - i; j++) {
  83. segm[j][j + i] = str.substr(j, i + 1);
  84. sort(segm[j][j + i].begin(), segm[j][j + i].end());
  85. }
  86. cin >> n;
  87. for (int i = 0; i < n; i++) {
  88. cin >> dict1[i];
  89. t = dict1[i];
  90. sort(t.begin(), t.end());
  91. dict2[t.length()].push_back(make_pair(t, i));
  92. }
  93. for (int i = 1; i <= 100; i++)
  94. sort(dict2[i].begin(), dict2[i].end(), cmp);
  95. solve(0, len - 1);
  96. if (dp[0][len - 1] == 0)
  97. cout << "impossible";
  98. else if (amb[0][len - 1])
  99. cout << "ambiguous";
  100. else
  101. rec(0, len - 1);
  102. return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement