HDU 4513 吉哥系列故事 完美队形II (manacher)_TaoSama的博客-程序员宝宝

技术标签: 字符串  字符串 - KMP | EXKMP | Manacher  manacher  

题意:

N<=105,,

分析:

p,#

代码:

//
//  Created by TaoSama on 2015-11-03
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 2e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, k, p[N];
int a[N], s[N];

int manacher() {
    s[0] = '@'; s[1] = '#'; n = 2;
    for(int i = 0; i < k; ++i)
        s[n++] = a[i], s[n++] = '#';
    s[n] = 0;

    int mx = 0, id, ret = 0;
    for(int i = 1; i < n; ++i) {
        p[i] = mx > i ? min(mx - i, p[2 * id - i]) : 1;
        while(s[i - p[i]] == s[i + p[i]]) {
            if(p[i] == 1 || s[i + p[i]] == '#') {}
            else {
                if(s[i + p[i]] > s[i + p[i] - 2]) break;
            }
            ++p[i];
        }
        if(mx < i + p[i]) mx = i + p[i], id = i;
        ret = max(ret, p[i] - 1);
    }
    return ret;
}

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    int t; scanf("%d", &t);
    while(t--) {
        scanf("%d", &k);
        for(int i = 0; i < k; ++i) scanf("%d", a + i);
        printf("%d\n", manacher());
    }
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lwt36/article/details/49623195

智能推荐

冒泡排序数组以及按位异或(^)——看程序员认知_愿 不忘初心的博客-程序员宝宝_数组按位异或

// for循环冒泡排序数组优化后 var arr = [10, 50, 70, 90, 20, 30]; for (var i = 0; i &amp;lt; arr.length - 1; i++) { var isOk = true; for (var j = 0; j &amp;lt; arr.length - 1 - i; j++) { ...

php环境搭建(正确配置nginx和php)_nana837的博客-程序员宝宝_php nginx

一.nginx实现php动态解析原理nginx 是一个高性能的http服务器和反向代理服务器。即nginx可以作为一个HTTP服务器进行网站的发布处理,也可以作为一个反向代理服务器进行负载均衡。但需要注意的是:nginx本身并不会对php文件进行解析。对PHP页面的请求将会被nginx交给FastCGI进程监听的IP地址及端口,由php-fpm(第三方的fastcgi进程管理器)作为动态解析服务器处理,最后将处理结果再返回给nginx。即nginx通过反向代理功能将动态请求转向后端php-fpm,从而实

链表,顺序表的逆置_追艺_年华的博客-程序员宝宝

带头结点的单链表逆置#include#include#include//函数状态码定义#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status

C++与Python之间跨进程通信(socket实现)_54渣渣shuo的博客-程序员宝宝_c++客户端和python服务器通信用什么框架

C++与Python之间跨进程通信(socket实现)1.引言2.实现思路3. 具体代码(1)Python服务端(2)C++客户端1.引言之前写过一篇Python调用C++程序的实现方法,这里相反,希望使用Python协助C++完成某些任务。一种解决思路为实现RPC调用,使用C++端(以下称客户端)发送数据,Python端(以下称服务端)处理数据并返回的方法,进一步来说,转换为C++与Python之间通信的问题。2.实现思路因为客户端可能希望使用的函数多种多样,这里为了保证灵活,服务端与客户端均

尤雨溪:VUE 3 之后会休息一下_Python研究所的博客-程序员宝宝

此文转载自:https://my.oschina.net/u/4487475/blog/4631827LiteOS Studio图形化调测能力,物联网打工人必备!&gt;&gt;&gt;9 月 19 日,VUE 终于迎来了 3.0 正式版。众所周知,VUE 的作者尤雨溪是一个资深的二次元爱好者。自 2014 年以来,VUE 的每个重要版本都会被赋予一个神秘代号。从 VUE...

墙裂推荐9个在线图片压缩网站_wayne214的博客-程序员宝宝_免费压缩图片的网站

转载自:https://www.zcool.com.cn/article/ZNTQzNDYw.html?switchPage=on1.Tinypng网址:https://tinypng.com/Tinypng可以说是很受大家欢迎的一个图片压缩站点,不管对于前端工程师或者设计师来说都是一个不错的图片压缩工具。Tinypng的操作方式也十分的简单,上传、压缩、下载,流程十分的简单,网站不仅仅支...

随便推点

L1-002. 打印沙漏_卤蛋不想敲代码的博客-程序员宝宝

L1-002. 打印沙漏 本题要求你写个程序把给定的符号打印成沙漏的形状。例如给定17个“*”,要求按下列格式打印***** *** * ********所谓“沙漏形状”,是指每行输出奇数个符号;各行符号中心对齐;相邻两行符号数差2;符号数先从大到小顺序递减到1,再从小到大顺序递增;首尾符号数相等。给定任意N个符号,不一定能正好组成一个沙漏。要求打印出的沙漏能用掉尽可...

Debugserver调试服务器error: failed to attach to process named: "" unable to start the exception thread..._Macle-VIP的博客-程序员宝宝_*error* failed to attach bridge /[email protected]/[email protected]

环境:iOS 10.2.1 iPad Pro(已越狱)拷贝手机上的debugserver 到电脑上#scp [email protected]:/Developer/usr/bin/debugserver ./使用ldid从新进行签名#ldid -e debugserver &gt; debugserver.entitlements#ldid -Sdebugserver....

time命令详情_weixin_34320724的博客-程序员宝宝

基础命令学习目录首页原文链接:https://blog.csdn.net/adaptiver/article/details/6596143?utm_source=blogxgwz3linux下time命令可以获取到一个程序的执行时间,包括程序的实际运行时间(real time),以及程序运行在用户态的时间(user time)和内核态的时间(sys time)。它的使用方...

HDU 1548 A strange lift(bfs或dijkstra)_asdfghjkl999999999的博客-程序员宝宝

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1548题意:每层电梯对应着一个一个数k[i](i为这层电梯的层号),你可以选择UP或者DOWN,若选择UP则上升k[i]层,若现在DOWN则下降k[i]层,需要注意的是下降或上升之后的层数需在1-n之内。如何用dijkstra实现:若i层楼梯可以上...

octmps报错_!呜呼啦呼!的博客-程序员宝宝

&gt;&gt;&gt;&gt;&gt;&gt;Simulation time: 1000.182007 (ms)/usr/local/lib/python2.7/dist-packages/traits/etsconfig/etsconfig.py:429: UserWarning: Environment variable "HOME" not set, setting home directory to /tmp (environment_variable, parent_directory))

Fiddler4 手机抓包_倩倩sweet的博客-程序员宝宝

1.要对计算机Fiddler进行配置,允许远程计算机连接。2.保证手机电脑在同一局域网中。3.手机上设置代理服务器。以华为手机为例,设置–&gt;WLAN–&gt;找到并长按目前所连接的WiFi–&gt;修改网络–&gt;勾选显示高级选项–&gt;代理–&gt;选择手动–&gt;输入FIddler所在主机IP及端口–&gt;确定。4.在手机上安装证书。(为了抓取https包)方法1:在手...

推荐文章

热门文章

相关标签