// Miroslaw #include<cstdio> #include<cstdlib> #include<cstring> #include<cctype> #include<cmath> #include<cassert> #include<iostream> #include<string> #include<vector> #include<set> #include<map> #include<list> #include<queue> #include<deque> #include<algorithm> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define FORD(i,a,b) for(int i=(a);i>=(b);i--) #define FOREACH(i,c) for(__typeof((c).begin())i = (c).begin();i!=(c).end(); ++i) int cond = 1; #define DB(X) {if(cond){cerr<<"Line:"<<__LINE__<<", "<<#X<<" = "<<X<<endl;}} #define DB2(X, Y) {if(cond){cerr<<"Line:"<<__LINE__<<", "<<#X<<" = "<<X<<", "<<#Y<<" = "<<Y<<endl;}} #define DB3(X, Y, W) {if(cond){cerr<<"Line:"<<__LINE__<<", "<<#X<<" = "<<X<<", "<<#Y<<" = "<<Y<<", "<<#W<<" = "<<W<<endl;}} #define DB4(X, Y, W, Z) {if(cond){cerr<<"Line:"<<__LINE__<<", "<<#X<<" = "<<X<<", "<<#Y<<" = "<<Y<<", "<<#W<<" = "<<W<<", "<<#Z<<" = "<<Z<<endl;}} #define DBP(X) {if(cond){cerr<<"Line:"<<__LINE__<<", "<<#X<<" = ("<<X.first<<", "<<X.second<<")" << endl;}} #define DBV(X) {if(cond){cerr<<"Line:"<<__LINE__<<", "<<#X<<": ";FOREACH(__i,X)cerr<<*__i<<" ";cerr<<endl;}} // Std. implementation of Manacher algorithm vector<int> manacher(const string& s, int parity) { vector<int> R(s.size(), 0); int i = 1, j = 0, c = 1; while (i <= s.size() - 1) { while (s[i - j - parity] == s[i + j + 1]) { j++; } R[c++] = j; int k = 1; while (R[i - k] != R[i] - k && k <= j) { R[c++] = min(R[i - k], R[i] - k); k++; } j=max(j - k, 0); i += k; } return R; } int main() { string s; cin >> s; int ms = -1, msloc = 0; vector<int> v = manacher("#" + s + "@", 0); for (int i = 1; i < v.size() - 1; ++i) { if (v[i] * 2 > ms) { ms = 2 * v[i]; msloc = i; } } // DBV(v); vector<int> v2 = manacher("#" + s + "@", 1); for (int i = 1; i < v2.size() - 1; ++i) { if (v2[i] * 2 + 1 > ms) { ms = 2 * v2[i] + 1; msloc = i; } } // DBV(v2); // DB2(ms, msloc); for (int i = msloc - ms / 2 - ms %2; i < msloc + ms / 2; ++i) { printf("%c", s[i]); } printf("\n"); return 0; }