Advertisement
bibaboba12345

Untitled

Oct 2nd, 2021
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.13 KB | None | 0 0
  1. #pragma GCC optimize ("Ofast")
  2. #pragma GCC target ("avx2")
  3. #define _CRT_SECURE_NO_WARNINGS
  4. #include <iostream>
  5. #include <string>
  6. #include <vector>
  7. #include <stack>
  8. #include <algorithm>
  9. #define endl '\n';
  10. using namespace std;
  11.  
  12. int n;
  13. string s,s1;
  14. vector<string> dp[100];
  15. vector <pair <string, string> > alph;
  16. int main()
  17. {
  18. #ifdef _DEBUG
  19. //freopen("input.txt", "r", stdin);
  20. #else
  21. ios_base::sync_with_stdio(false);
  22. cin.tie(0);
  23. cout.tie(0);
  24. #endif
  25. cin >> n;
  26. alph.resize(n);
  27. for (long long i = 0; i < n; i++) {
  28. cin >> alph[i].first >> alph[i].second;
  29. }
  30. cin >> s;
  31. dp[0].push_back("");
  32.  
  33. for (int i = 0; i < s.size(); i++) {
  34. if (!dp[i].empty()) {
  35. for (int j = 0; j < n; j++) {
  36. s1 = alph[j].first;
  37.  
  38. if (s1.size() + i <= s.size()) {
  39. bool z = true;
  40. for (int j1 = i; j1 < i + s1.size(); j1++) {
  41. if (s[j1] != s1[j1 - i]) {
  42. z = false;
  43. break;
  44. }
  45. }
  46. if (z) {
  47. dp[i + s1.size()].push_back(dp[i][0] + alph[j].second);
  48. }
  49. }
  50. }
  51. }
  52. }
  53. if (dp[s.size()].empty()) {
  54. cout << "NO ANSWER";
  55. }
  56. else {
  57. cout << dp[s.size()][0];
  58. }
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement