传送门

manacher......

先跑一边manacher是必须的

然后枚举双倍回文串的对称轴x

把这个双倍回文串分成4段,w wR w wR

发现,只有当 y <= x + p[x] / 2 && y - p[y] <= x 时,y最大才是最优解

也就是y在第三段,并且以y为中心的回文串要扩展到x的或左边,并且y的回文串要被x的包在里面

那么 (y-x) * 4 中最大的就是答案

我们不妨按照 y - p[y] 排序y,枚举x,依次添加y进入set,从set中找最大的 y <= x + p[x] / 2

边界讨论恶心至极

#include <set>
#include <cstdio>
#include <algorithm>
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
#define N 1100000 int n, pos, maxright, ans;
int p[N], f[N];
char s[N];
std::set <int> S;
std::set <int> :: iterator it; struct node
{
int id, p;
}a[N]; inline bool cmp(node x, node y)
{
return x.p < y.p;
} inline void manacher()
{
int i;
s[0] = '$', s[n * 2 + 1] = '#';
for(i = n; i >= 1; i--) s[i * 2] = s[i], s[i * 2 - 1] = '#';
for(i = 1; i <= n * 2 + 1; i++)
{
p[i] = 1;
if(i <= maxright)
p[i] = min(p[pos * 2 - i], maxright - i + 1);
while(s[i - p[i]] == s[i + p[i]]) p[i]++;
if(maxright < i + p[i] - 1)
{
pos = i;
maxright = i + p[i] - 1;
}
}
for(i = 1; i <= n; i++) f[i] = (p[i * 2 - 1] - 1) / 2;
} int main()
{
int i, j;
scanf("%d", &n);
scanf("%s", s + 1);
manacher();
for(i = 1; i <= n; i++) a[i].id = i, a[i].p = i - f[i];
std::sort(a + 1, a + n + 1, cmp);
j = 1;
for(i = 1; i <= n; i++)
{
while(a[j].p <= i && j <= n)
S.insert(a[j].id), j++;
it = S.upper_bound(i + f[i] / 2);
if(it == S.begin()) continue;
it--;
ans = max(ans, (*it - i) * 4);
}
printf("%d\n", ans);
return 0;
}

  

最新文章

  1. while用法一例
  2. 分享 Ionic 开发 Hybrid App 中遇到的问题以及后期发布 iOS/Android 的方方面面
  3. php集成动态口令认证
  4. 在linux中减小和增大LV的过程与思考
  5. Hdu 1081 To The Max
  6. Java_解决java.security.cert.CertificateException: Certificates does not conform to algorithm constraints
  7. Ant -- Another Neat Tool
  8. selenium+python登录登出百度,等待页面加载,鼠标定位
  9. xampp环境安装swoole
  10. 【转】从框架看PHP的五种境界及各自的薪资待遇
  11. linux根据该文件夹的读取权限和权限运行差异
  12. 开始PYTHON之路
  13. JVM(一):方法区
  14. HotSpot 虚拟机对象揭秘【转载】
  15. .NET拾忆:FileSystemWatcher 文件监控
  16. NATS—协议详解(nats-protocol)
  17. bzoj 2753 [SCOI 2012] 滑雪与时间胶囊 - Prim
  18. 简单的java程序
  19. Grapher - Change how graphs look
  20. 移动端使用的WebKit私有属性(转)

热门文章

  1. php通过类名查找这个类所在的路径(即实际引用的是哪个类)
  2. vue.js与react.js相比较的优势
  3. 转载自infoq:MYSQL的集群方案
  4. Codeforces Round #290 (Div. 2) _B找矩形环的三种写法
  5. charles连接手机抓包--------最详细的步骤
  6. video 的使用
  7. Java MiniUi datagrid加载数据时,如果使用virtualScroll=&quot;false&quot;,数据多一点可能就会加载不出来
  8. Python基础篇 -- 列表
  9. 【dp 贪心】bzoj4391: [Usaco2015 dec]High Card Low Card
  10. 【curl】【php】curl报错,错误代码77,CURLE_SSL_CACERT_BADFILE (77)解决方法