本文共 1222 字，大约阅读时间需要 4 分钟。

双倍回文

题目链接： /

题目大意

要在字符串里面找一个子串，使得它能被分为完全相同的两半。而且这两半应该是回文串，而且长度是偶数。

找最大的这种子串，输出最大的长度。

思路

首先看到回文串，把马拉车模板搞出来。

然后再看。

其实根据题目，可以看出，这个大的子串也是回文串，而且长度也是偶数。 那为奇数的回文串全部没用，也不能用，就不用算。

那你考虑在跑马拉车的时候就把答案算出来。

那你想，你要看三个回文串，那肯定是在第三个处理，因为这个时候前两个都求出来了。 那要什么条件呢？ 首先，它中心要在大回文串的右端点的左边，这样，它才有机会被包含在里面。那你大回文串选什么呢？为了让结果都找到，肯定是要右端点最大的。那就是马拉车里面的 $maxr$ 了。 那而且，它的左边是要在大回文串中心的左边，这样它才可以覆盖玩大回文串右边的整个区域。

那可以的话，我们就确定了大回文串的右边的范围：从大回文串的中心到它的中心。（它是右边的小回文串）

那就可以算出这个符合的子串的长度。

那你把找到的都去最大值，那就是答案了。

代码

#include
   
    #include
    
     using namespace std;int n, f[1500001], ans;char c[1500001], s[500001];void Manacher() {   	int maxn = 0, maxr = 0;	for (int i = 1; i <= n; i += 2) {   //因为规定回文串重心一定是#，另一种就不能用了		if (2 * maxn - i > 0) f[i] = min(f[2 * maxn - i], maxr - i);			else f[i] = maxr - i;		f[i] = max(1, f[i]);				if (i < maxr && i - f[i] < maxn)//看着是否能成为规定的串			ans = max(ans, (i - maxn) * 2);				while (i - f[i] >= 1 && i + f[i] <= n && c[i - f[i]] == c[i + f[i]])			f[i]++;				if (i + f[i] > maxr) {   			maxr = i + f[i];			maxn = i;		}	}}int main() {   	scanf("%d", &n);	scanf("%s", s + 1);		c[1] = '#';	for (int i = 1; i <= n; i++) {   		c[i << 1] = s[i];		c[i << 1 | 1] = '#';	}		n = n << 1 | 1;	Manacher();		printf("%d", ans);		return 0;}
    
   

转载地址：http://oavh.baihongyu.com/