H4_mine.cpp

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

int Z, n, R[MAX], id, max_value, j, k;
string text, result;
bool ok;

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 = "";
  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 t = 1;
  R[1] = 0;
  for (int i = 2; i <= n; i++) {
    j = t-(i-t);
    if (t+R[t] >= i) k = min(R[j], t+R[t]-i);
    else k = 0;

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

    if (k >= max_value && i - k == 0) {
      max_value = k;
      id = i;
    }
    else if (k >= max_value && i + k == n) {
      max_value = k;
      id = i;
    }   

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

void calculate() {
  manacher();

  ok = true;
  for (int i = 1; i < n; i++) if (text[i] != text[n-1]) ok = false;

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

  //3
  if ((id >= n/2) && (id + max_value == n)) {
    result = text;
    for (int i = id - max_value; i > 0; i--) result += text[i];
    return;
  }

  //4
  result = text;
  for (int i = n-2; i >= 1; i--) result += text[i];
}

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