///////////////////////////求最长回文子串的算法，时间复杂度 O(NlogN)/////////////////////////////
#include <stdio.h>
#define LEN 30
typedef struct sfx
{
int offset, key[2];
} Sfx;
int compare(const void *a, const void *b)
{
Sfx *sa = (Sfx*)a;
Sfx *sb = (Sfx*)b;
if(sa->key[1] < sb->key[1])
return -1;
else if(sa->key[1] == sb->key[1])
return 0;
else
return 1;
}
/////////////定义队列///////////////////
typedef struct queue
{
Sfx s[LEN];
int head, tail;
} Queue;
void clear(Queue *q)
{
q->head = q->tail = 0;
}
int empty(Queue *q)
{
if(q->head == q->tail)
return 1;
return 0;
}
int full(Queue *q)
{
if((q->tail+1)%LEN == q->head)
return 1;
return 0;
}
Sfx top(Queue *q)
{
return q->s[q->head];
}
void pop(Queue *q)
{
if(!empty(q))
q->head = (q->head+1)%LEN;
}
void push(Queue *q, Sfx e)
{
if(full(q))
pop(q);
q->s[q->tail] = e;
q->tail = (q->tail+1)%LEN;
}
////////////////////////////////////////////////////
Sfx sfx[LEN];
int rank[LEN];
Queue qs[LEN];
int height[LEN];
int st[LEN][LEN];
void radix_sort(int n) //基数排序
{
int count = 0, i;
for(i = 0; i < n; ++i)
{
if(i == n-1 || sfx[i].key[0] != sfx[i+1].key[0])
{
if(count)
{
push(&qs[sfx[i].key[1]], sfx[i]);
int j, k = i-count;
for(j = 0; j <= n; ++j)
while(!empty(&qs[j]))
{
sfx[k++] = top(&qs[j]);
pop(&qs[j]);
}
count = 0;
}
}
else
{
++count;
push(&qs[sfx[i].key[1]], sfx[i]);
}
}
}
void build_sa(char *str, int n) // 建立后缀数组
{
int i;
for(i = 0; i < n; ++i)
{
sfx[i].offset = i;
sfx[i].key[0] = 0;
sfx[i].key[1] = str[i];
}
qsort(sfx, n, sizeof(Sfx), compare);
int r = 1;
while(r < n)
{
int k = 0, temp = sfx[0].key[0];
rank[sfx[0].offset] = sfx[0].key[0] = 0;
for(i = 1; i < n; ++i) // 更新 key[0] 和 rank
{
++k;
if(sfx[i].key[1] == sfx[i-1].key[1] && sfx[i].key[0] == temp)
{
temp = sfx[i].key[0];
rank[sfx[i].offset] = sfx[i].key[0] = sfx[i-1].key[0];
}
else
{
temp = sfx[i].key[0];
rank[sfx[i].offset] = sfx[i].key[0] = k;
}
}
for(i = 0; i < n; ++i) // 更新 key[1]
{
int d = sfx[i].offset + r;
if(d >= n)
sfx[i].key[1] = 0;
else
sfx[i].key[1] = rank[d] + 1;
}
radix_sort(n);
r *= 2;
}
}
int get_prefix(char *a, char *b)
{
int i;
for(i = 0; i < strlen(a) && i < strlen(b); ++i)
if(a[i] != b[i])
return i;
return i;
}
void get_height(char *str, int n) // 建立 height数组
{
int i;
for(i = 0; i < n; ++i)
{
if(rank[i] == 0)
height[rank[i]] = 0;
else if(i == 0 || height[rank[i-1]] <= 1)
height[rank[i]] = get_prefix(str+i, str+sfx[rank[i]-1].offset);
else
{
int temp = height[rank[i-1]]-1;
height[rank[i]] = temp+get_prefix(str+i+temp, str+sfx[rank[i]-1].offset+temp);
}
}
}
#define MIN(x, y) (x)<(y)?(x):(y)
#define SWAP(x, y) x = x+y-(y=x)
int get_st(int *h, int n) // 建立 sparse table 用于 RMQ (Range Minimum/Maximum Query)
{
int i, j;
for(i = 0; i < n; ++i)
st[i][0] = h[i];
for(j = 1; 1<<j <= n; ++j)
for(i = 0; i+(1<<j)-1 < n; ++i)
st[i][j] = MIN(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
int get_lcp(int i, int j) // 通过已建立的 sparse table 确定指定两后缀间的最长公共前缀的长度
{
if(i > j)
SWAP(i, j);
else if(i == j)
return 0;
int k = (int)log2(j-i);
return MIN(st[i+1][k], st[j-(1<<k)+1][k]);
}
#define odd 1
#define even 0
void find_mlp(char *str, const char *org, int n) // 找出最长回文子串 (Most Longest Palindrome)
{
typedef struct mark
{
unsigned type;
unsigned len;
unsigned offset;
} Mark;
Mark m = {odd, 0, 0};
int i, nn = n*2, lcp;
for(i = n-1; i >= 0; --i)
{
lcp = get_lcp(rank[i], rank[nn-i]);
if(lcp > m.len)
{
m.len = lcp;
m.offset = i;
m.type = odd;
}
if(i != 0)
{
lcp = get_lcp(rank[i], rank[nn-i+1]);
if(lcp > m.len || (lcp == m.len && m.type == odd))
{
m.len = lcp;
m.offset = i;
m.type = even;
}
}
}
if(m.len != 0)
{
int len;
if(m.type == odd)
strncpy(str, org+m.offset-m.len+1, len = m.len*2-1);
else
strncpy(str, org+m.offset-m.len, len = m.len*2);
str[len] = 0;
}
else
*str = 0;
}
void mlp(char *str, char *org, int n) // 综合过程
{
int i;
for(i = 1; i <= n; ++i)
org[n+i] = org[n-i];
int m = 2*n+1;
org[m] = 0;
build_sa(org, m);
get_height(org, m);
get_st(height, m);
find_mlp(str, org, n);
}
int main(void)
{
char str[100];
scanf("%s", str);
char res[100];
mlp(res, str, strlen(str));
printf("%s\n", res);
getch();
return 0;
}
