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

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

题意:

$N<=10^5的串, 求最长回文串, 并且左边的部分是不降的$

分析:

$计算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;
}

本文链接：https://blog.csdn.net/lwt36/article/details/49623195

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

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

// for循环冒泡排序数组优化后 var arr = [10, 50, 70, 90, 20, 30]; for (var i = 0; i &lt; arr.length - 1; i++) { var isOk = true; for (var j = 0; j &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图形化调测能力，物联网打工人必备！>>>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 > debugserver.entitlements#ldid -Sdebugserver....