laekov

以前觉得不会，仔细想想觉得还是挺水。

manacher找出所有中心回文串，然后用单调队列扫一下每个位置往左最长和往右最长就行。找位置比较烦不过还是比较好写的。

重点是写出了在windows下拿for循环对拍，虽然异常丑。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 200009;

int n, l[maxn], q[maxn], vx[maxn], vy[maxn];

char a[maxn];

void manacher() {

l[0] = 1;

for (int i = 1, j = 0; i < (n << 1) - 1; ++ i) {

int r = ((j + 1) >> 1) + l[j] - 1;

int p = i >> 1, q = i - p;

l[i] = (r >= q) ? min(r - q + 1, l[(j << 1) - i]) : 0;

while (p - l[i] >= 0 && q + l[i] < n && a[p - l[i]] == a[q + l[i]])

++ l[i];

if (q + l[i] - 1 > r)

j = i;

}

}

#define getLeft(x) (((x)>>1)-l[x]+1)

#define getRight(x) ((((x)+1)>>1)+l[x]-1)

void dp(bool d) {

static int q[maxn];

int hd = 0, tl = 0;

if (!d) {

for (int i = 0; i < n; ++ i) {

if (!tl || getRight(i << 1) > getRight(q[tl - 1]))

q[tl ++] = (i << 1);

while (getRight(q[hd]) < i)

++ hd;

vx[i] = (i << 1) - q[hd] + 1;

if (i < n - 1 && getRight((i << 1) + 1) > getRight(q[tl - 1]))

q[tl ++] = (i << 1) + 1;

}

}

else {

for (int i = n - 1; i >= 0; -- i) {

if (!tl || getLeft(i << 1) < getLeft(q[tl - 1]))

q[tl ++] = (i << 1);

while (getLeft(q[hd]) > i)

++ hd;

vy[i] = q[hd] - (i << 1) + 1;

if (i && getLeft((i << 1) -1) < getLeft(q[tl - 1]))

q[tl ++] = (i << 1) - 1;

}

}

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

scanf("%s", a);

n = strlen(a);

manacher();

dp(0);

dp(1);

int ans = 2;

for (int i = 1; i < n; ++ i)

ans = max(ans, vx[i - 1] + vy[i]);

printf("%d\n", ans);

}