H4_mine.cpp

#include<iostream>
#include<cstring>
#define MAX 4000001
using namespace std;

int Z, n, R[MAX], id, max_value;
string text, result;

void load_data_and_cleaning();
void calculate();
void print_data();

int main(int argc, const char *argv[]) {
  cin >> Z;
  while(Z--) {
    load_data_and_cleaning();
    calculate();
    print_data();
  }
  return 0;
}

void load_data_and_cleaning() {
  result = "";
  id = max_value = 0;
  string tmp;
  cin >> tmp;
  text.resize(2*tmp.length());

  for (int i = 0; i < text.length()-1; i++) {
    text[i] = '#';
    text[i+1] = tmp[i/2];
    i++;
  }
  
  text = text + '#';
  n = text.length() - 1;
}

void manacher() {
  int l;
  int t = 1;
  R[1] = 0;
  for (int i = 2; i <= n; i++) {
    if (t+R[2*t-i] >= i) l = min(t+R[t]-i, R[2*t-i]);
    else l = 0;

    while (i+l < n && i-l > 0 && text[i+l] == text[i-l]) l++;
    R[i] = l;

    if (l >= max_value && i == l) {
      max_value = l; id = i;
    }
    else if (l >= max_value && i + l == n) {
      max_value = l; id = i;
    }   

    if (i+R[i] > t+R[t]) t = i;
  }
}

void calculate() {
  manacher();

  if (id >= n/2) {
    result = text;
    for (int i = id - max_value; i > 0; i--) result += text[i];
  }
  else {
    for (int i = n; i > 0; i--) result += text[i];
    for (int i = id + max_value + 1; i <= n; i++) result += text[i];
  }
}

void print_data() {
  for (int i = 0; i < result.length(); i++) {
    if (result[i] != '#') cout << result[i];
  }
  cout << endl;
}