fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string transform(string& s) {
  5.     string ret;
  6.     ret.push_back('^');
  7.     for(int i=0;i<s.size();i++) {
  8.         ret.push_back(s[i]);
  9.         if(i+1<s.size()) ret.push_back('_');
  10.     }
  11.     ret.push_back('$');
  12.     return ret;
  13. }
  14.  
  15. string longest(string& _s) {
  16.     string s = transform(_s); // transform string to ^a_a_b_b_a_a$ so every palindrome is odd length
  17.     int n = s.size();
  18.     int best=0;
  19.     vector<int> pal(n,0);
  20.     int l=1,r=1; // rightmost palindrome atm
  21.     for(int i = 1; i < n-1; i++) {
  22.         pal[i] = min(pal[l+(r - i)], r - i); // set palindrome (half) length at center i to the mirrored string's length (capped at r)
  23.         while(s[i - pal[i]] == s[i + pal[i]]) pal[i]++; // increase palindrome length if possible
  24.         if(i + pal[i] > r) {
  25.             // update rightmost palindrome end
  26.             l = i - pal[i];
  27.             r = i + pal[i];
  28.         }
  29.         // update best palindrome
  30.         if(pal[i] >= pal[best]) best = i;
  31.     }
  32.     string ans = "";
  33.     for(int i=best-pal[best]+1;i<best+pal[best];i++) if(s[i] != '_') ans.push_back(s[i]);
  34.     return ans;
  35. }
  36.  
  37. string longest(vector<string>& str) {
  38.     string best;
  39.     for(auto& s : str) {
  40.         auto ss = longest(s);
  41.         cout<<ss<<endl;
  42.         if(ss.size() > best.size()) best = ss;
  43.     }
  44.     return best;
  45. }
  46.  
  47. int main() {
  48.     vector<string> v = {"carracecar", "aabbaa", "aabbbabab"};
  49.     cout<<longest(v)<<endl;
  50. }
  51.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
racecar
aabbaa
abbba
racecar
https://ideone.com/e0P0AV
language:
C++14 (gcc 8.3)
created:
7 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!