fork download
copy 
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8.  
  9. string Manacher(string s){
  10.     int n = (int)(s.size());
  11.  
  12.     vector<int> d1(n);
  13.     for (int i = 0, l = 0, r = -1; i < n; i++) {
  14.         int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
  15.         while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
  16.             k++;
  17.         }
  18.         d1[i] = k--;
  19.         if (i + k > r) {
  20.             l = i - k;
  21.             r = i + k;
  22.         }
  23.     }
  24.  
  25.     vector<int> d2(n);
  26.     for (int i = 0, l = 0, r = -1; i < n; i++) {
  27.         int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
  28.         while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
  29.             k++;
  30.         }
  31.         d2[i] = k--;
  32.         if (i + k > r) {
  33.             l = i - k - 1;
  34.             r = i + k ;
  35.         }
  36.     }
  37.  
  38.     int maxLen = 1;
  39.     for(int i = 0; i < n; i++){
  40.         if(d1[i] == i+1)
  41.             maxLen = max(maxLen, 2*i+1);
  42.         if(d2[i] == i)
  43.             maxLen = max(maxLen, 2*i);
  44.     }
  45.     return s.substr(0,maxLen);
  46. }
  47.  
  48.  
  49. int main() {
  50.     string s;
  51.     cin >> s;
  52.     cout << Manacher(s);
  53.     return 0;
  54. }
Success #stdin #stdout 0s 4484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9J9u2c
language:
C++14 (gcc 8.3)
created:
4 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!