1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const double pi = acos(-1.0);
// t = a+b
// t = s[pre] + s[suffix]
// len(t) <= len(s)
// ==>
//
// [preA][...]...[~preA]
// [preA]...[...][~preA]
//
//
// = s 移除连续一段 使得结果变成回文
// s[....]
// ~s[....]
// dp[i][j] [0/1/2][0/1/2]
// n^2 ?
//
// s[...i[ ]i...]
// = max(2*i+ [i+1...]回文 ])
// = max(2*i+ [ ...[...?]回文] )
char s[1'000'010];
char t1[1'000'010];
char t2[1'000'010];
int pre[1'000'010];
int r(char * ch,int sz){
pre[0] = -1;
rep(i,1,sz){
int pos = i-1;
while(true){
pos = pre[pos];
if(ch[pos+1] == ch[i]){
pre[i] = pos+1;
break;
}
if(pos == -1){
pre[i] = -1;
break;
}
}
}
// rep(i,0,sz){
// printf("%d ",pre[i]);
// }
int lastans = -1;
per(i,0,sz){
// [[0..lastans]..i[..0]...]
while(true){
if(ch[i] == ch[lastans+1]){
if(lastans + 2 >= i){
return lastans*2+3+ (i!=lastans+1);
}
lastans++;
break;
}
if(lastans == -1){
break;
}
lastans = pre[lastans];
}
}
return 0;
}
int main(){
int t;
cin>>t;
while(t--){
scanf("%s",s);
int n = strlen(s);
int k = -1;
rep(i,0,n){
if(i<n-1-i){
if(s[i]==s[n-i-1]){
k = i;
}else{
break;
}
}
}
rep(i,k+1,n-k-1){
t1[i-k-1]=s[i];
}
int len1 = r(t1,n-2-2*k);
rep(i,k+1,n-k-1){
t2[n-k-2-i]=s[i];
}
int len2 = r(t2,n-2-2*k);
// cout<<"?"<<len1<<endl;
// cout<<"!"<<len2<<endl;
rep(i,0,k+1){
printf("%c",s[i]);
}
if(len1 > len2){
rep(i,0,len1){
printf("%c",t1[i]);
}
}else{
rep(i,0,len2){
printf("%c",t2[i]);
}
}
rep(i,n-k-1,n){
printf("%c",s[i]);
}
printf("\n");
}
return 0;
}
|