<div class="post_brief"><p>
久了不写manacher又手生了只好抄红书了。</p>

 

后面的过程就是对每个位置i找一个最远的位置j满足j在i为中心的回文子串的一半以内且j最小。然后直接拿个set就能搞定。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;


const int maxn = 500009;


char a[maxn];
int d[maxn << 1], n;


void manacher() {
d[0] = 1;
for (int i = 1, j = 0; i < (n << 1) - 1; ++ i) {
int p(i >> 1), q(i - p), r(((j + 1) >> 1) + d[j] - 1);
if (r < q)
d[i] = 0;
else
d[i] = min(r - q + 1, d[(j << 1) - i]);
while (p - d[i] >= 0 && q + d[i] < n && a[p - d[i]] == a[q + d[i]])
++ d[i];
if (q + d[i] - 1 > r)
j = i;
}
}


int pr[maxn];
inline int getr(int x) {
return x+d[((x)<<1)+1];
}
inline bool cmpRight(const int& a, const int& b) {
return getr(a) < getr(b);
}


set <int> rg;
int sov() {
int ans(0);
for (int i = 0; i < n - 1; ++ i)
pr[i] = i;
sort(pr, pr + n - 1, cmpRight);
for (int i = 0, k = 0; k < n; ++ k) {
for (; i < n - 1 && getr(pr[i]) < k; ++ i)
rg. erase(pr[i]);
set <int> :: iterator it = rg. lower_bound(k - (d[(k << 1) + 1] >> 1));
if (it != rg. end())
ans = max(ans, k - *it);
rg. insert(k);
}
return ans * 4;
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


scanf("%d%s", &amp;n, a);
manacher();
printf("%d\n", sov());



}