fork download
  1. #include <iostream>
  2. #include <cassert>
  3. #include <algorithm>
  4. #include <array>
  5. #include <string>
  6. #include <unordered_map>
  7. #include <chrono>
  8.  
  9. // S('t' "alpha" 'h')
  10. std::string palindrome(const std::string& s) {
  11. // so slow ... trying to search in cache
  12. static std::unordered_map<std::string, std::string> cache;
  13. if (cache.find(s) != end(cache)) {
  14. return cache[s];
  15. }
  16. //////////////////////////////////////////
  17. if (s.size() == 0 || s.size() == 1) {
  18. return s;
  19. }
  20. std::string alpha{ s.substr(1, s.size() - 2) };
  21. if (s.front() == s.back()) {
  22. std::string result = s.front() + palindrome(alpha) + s.back();
  23. cache[s] = result;
  24. return result;
  25. }
  26. std::array<std::string, 3> branches;
  27. // S(alpha t)
  28. std::string alpha_t{ s.substr(1) };
  29. branches[0] = palindrome(alpha_t);
  30. if (branches[0].size() == alpha_t.size()) {
  31. cache[s] = branches[0];
  32. return branches[0];
  33. }
  34. // S(h alpha)
  35. std::string h_alpha{ s.substr(0, s.size() - 1) };
  36. branches[1] = palindrome(h_alpha);
  37. if (branches[1].size() == h_alpha.size()) {
  38. cache[s] = branches[1];
  39. return branches[1];
  40. }
  41. // S(alpha)
  42. branches[2] = palindrome(alpha);
  43.  
  44. auto result = std::max_element(branches.begin(), branches.end(), []
  45. (const std::string& a, const std::string& b) {
  46. return a.size() < b.size();
  47. });
  48.  
  49. cache[s] = *result;
  50. return *result;
  51. }
  52. int main()
  53. {
  54. std::ios_base::sync_with_stdio(false);
  55. std::string str;
  56. std::cin>>str;
  57. std::cout<<palindrome(str);
  58. }
Success #stdin #stdout 0s 3472KB
stdin
MOTTO
stdout
OTTO