fork download
copy 
  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
comments (?)
stdin
copy 
MOTTO
stdout
copy 
OTTO
https://ideone.com/mOYj62
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!