H4.cpp

#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#define INF 2000000000
#define MAX 1000000
using namespace std;

int Z;
string text, text2, result;
int tmp1_max_val, tmp1_max_id, tmp2_max_val, tmp2_max_id;

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

int main(int argc, const char *argv[]) {
  scanf("%d", &Z);
  while(Z--) {
    load_data_and_cleaning();
    calculate();
    print_data();
  }
  return 0;
}

void load_data_and_cleaning() {
  cin >> text;

  tmp1_max_val = tmp1_max_id = tmp2_max_val = tmp2_max_id = -1;
}

int* manacher(string s) {
  string x("$"); x += s; x += '@'; 
  //cout << "X: " << x << endl;
  int m[1000];
  int l = 1;
  m[0] = 0;
  int i = 1, j = 0;
  while (i <= x.size() - 1) {
    while (x[i - j - 1] == x[i + j + 1]) j++;
    m[l] = j; l++;
    int k = 1;
    while (m[i - k] != m[i] - k && k <= j) {
      int a = min(m[i - k], m[i] - k);
      m[l] = a; l++; k++;
    }

    if(i + j == text2.length() && j > tmp1_max_val) {
      tmp1_max_val = j;
      tmp1_max_id = i;
      //cout << "OK1: " << tmp1_max_id << " i " << tmp1_max_val << endl;
    }

    if(i == j + 1 && j > tmp2_max_val) {
      tmp2_max_val = j;
      tmp2_max_id = i;
      //cout << "OK2: " << tmp2_max_id << " i " << tmp2_max_val << endl;
    }

  //cout << "[" << i << "]" << " j: " << j << endl;
    j = max(j - k, 0); i += k;
  }
  return m;
}

string pong_begin(string &x, int r) {
  //cout << "I want to make, r: " << r << " and " << x << endl;

  string res; res.resize(x.length() + r);
  
  for (int i = 0; i < x.length(); i++) res[i] = x[i];
  for (int i = 0; i < r; i++) res[x.length()+i] = x[r-i-1];
  
  return res;
}

string pong_end(string &x, int r) {
  //cout << "I want to make, r: " << r << " and " << x << endl;
  string res; res.resize(x.length() + r);
  
  for (int i = 0; i < r; i++) res[i] = x[x.length()-i-1];
  for (int i = 0; i < x.length(); i++) res[r+i] = x[i];

  return res;
}

void calculate() {
  text2.resize(text.length()*2 - 1);

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

  int r1, r2;

  int* cos = manacher(text2);

  for (int i = 0; i <= text2.length(); i++) {
    cout << "[" << i << "]" << cos[i] << endl;
  }

  //cout << "R1: " << tmp1_max_id << " " << tmp1_max_val << endl;
  //cout << "R2: " << tmp2_max_id << " " << tmp2_max_val << endl;

  if (tmp1_max_id % 2 == 0) {
    r1 = text.length() - 2*(tmp1_max_val/2);
    if (tmp1_max_val % 2 == 1) r1++;
  }
  else r1 = text.length() - 1 - tmp1_max_val;

  if (tmp2_max_id % 2 == 0) {
    r2 = text.length() - 2*(tmp2_max_val/2);
    if (tmp2_max_val % 2 == 1) r2++;
  }
  else r2 = text.length() - 1 - tmp2_max_val;

  //cout << r1 << " vs " << r2 << endl;

  //cout << res1 << endl;
  //cout << res2 << endl;

  
  if (r1 < 0 || r2 < 0) {
    result = text;
  }
  else {
    if (r1 < r2) result = pong_begin(text, r1);
    else result = pong_end(text, r2);


    cout << "r1: " << r1 << " " << pong_begin(text, r1) << endl;
    cout << text.length() << " " << tmp1_max_val << " dla " << tmp1_max_id << endl;
    cout << "r2: " << r2 << " " << pong_end(text, r2) << endl;
    cout << text.length() << " " << tmp2_max_val << " dla " << tmp2_max_id << endl;
  }
}


void print_data() {
  cout << result << endl;
}