#include using namespace std; #define rep(i, n) for (int i=0; i manacher(string s) { int n = s.size(); vector res(n); int i = 0; int j = 0; while (i=0 && i+j=0 && k+res[i-k]> S; string T; for (char c : S) { T += '&'; T += c; } vector mana = manacher(T); int n = S.size(); bool is_pal[n][n+1]; rep(l, n) for (int r=l+1; r<=n; r++) { int center = l+r; is_pal[l][r] = 2*r-11) { int mid = (ok+ng)/2; bool dp[n+1]; dp[0] = true; rep(i, n) { if (!dp[i]) continue; for (int j=i+mid; j<=n; j++) if (is_pal[i][j]) dp[j] = true; } if (dp[n]) ok = mid; else ng = mid; } cout << ok << endl; }