BZOJ2342 [Shoi2011]双倍回文

久了不写manacher又手生了只好抄红书了。

后面的过程就是对每个位置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", &n, a);
	manacher();
	printf("%d\n", sov());
}