技术标签： 字符串 字符串 - 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;
}文章浏览阅读7.8k次，点赞35次，收藏93次。本文采用的方法称之为：ESP-IDF + Vscode开发方法，此方法成功的将 `ESP-IDF` 工具与编译工具分离，因此可以单独维护，关于ESP-IDF的版本切换可直接使用git切换即可，十分的方便，同时编辑器还是采用Vscode，编写代码还是很方便此外，本文除了阐述如何搭建开发环境之外，还记载了博主关于ESP32开发过程中的相关笔记，主要介绍了如何采用ESP32的开发风格开始搭建我们自己的工程进行开发。_esp32 idf vscode
文章浏览阅读275次，点赞3次，收藏5次。一、智慧工地监管端功能1.数据统计分析：工地数据分析、项目人员分析、危大工程分析、环境监测分析、安全隐患分析。2.项目人员监管：项目管理、班组管理、劳务人员管理、证件管理、考勤管理、考勤明细、考勤日期设置、工资管理、疫情进出场统计、在岗履职统计、教育培训、企业良好行为、企业不良行为、个人不良行为、个人良好行为、项目授权。3.视频监控监管：视频监控查看、智能视频AI分析、视频执法记录。4.危大工程监管：实时监测报警、机械设备司机识别、塔机监测、升降机监测、高支模监测、基坑监测。_智慧工地信息管理平台源码
文章浏览阅读9.9k次，点赞3次，收藏38次。电脑经常卡顿，就会严重影响了大家的工作效率，其实你的电脑可以开启“加速”优化设置来提升电脑的性能，今天小编就来给大家分享四个能减少电脑卡顿的实用小技巧，让电脑焕然一新，还不赶紧来试一试？一、调整电脑处理器性能首先，在桌面中右击「此电脑」，选择「属性」，进入页面后选择「高级系统设置」，在性能选项中进入「设置」，然后我们在视觉效果中选择「调整为最佳性能」。随后回到性能选项页面...
文章浏览阅读2.1k次。在深度学习中，选择合适的模型复杂度和训练数据量对于获得具有良好泛化性能的模型至关重要。本文讨论了模型参数量与训练数据量之间的关系，以及如何在实际应用中找到合适的平衡。通过采用交叉验证、学习曲线等方法评估模型泛化性能，并使用数据增强和正则化技术优化模型，可以有效提高模型在未知数据上的表现。_训练数据量和模型性能
文章浏览阅读289次。有些公司内部存在一些NET项目，而公司服务器后期都换成了Linux，若单纯为这一个项目占用一台Windows服务器显得极其浪费，因此需要将NET项目嵌入到Linux服务器中，为了后期方便迁移和运维最好是Docker容器中运行。新的.net core都已经支持docker，手头有一些原来开发的asp.net旧项目，用的asp.netmvc开发的，跑在.net formwork 4.6上。我们的web项目要想运行，需要有一个像IIS一种的服务器组件，在这里有两层意思：1.Net。
文章浏览阅读249次。我想很多的朋友都遇到过这样的问题，特别是在亲友群里面，很多时候别人发了红包自己却不知道！很难受........还有一种情况：当自己一直喜欢的女神发给自己一个消息的时候，还没来得及看，就撤回了。是不是自己在心中"YY"，她是不是发了什么，然后你问她的时候，她却说没什么。但是！！！！！强大的Python以及强大的程序员可以帮你解决这个问题！！！！！用Python开发一个微信小助手主要包括以下功能：1....
文章浏览阅读851次。算筹简述（相关链接：http://hi.hnjs.org/t/2993235） 中国春秋时代就出现了”算筹”根据史书的记载和考古材料的发现，古代的算筹实际上是一根根同样长短和粗细的小棍子，一般长为13--14cm，径粗0．2～0．3cm，多用竹子制成，也有用木头、兽骨、象牙、金属等材料制成的，大约二百七十几枚为一束，放在一个布袋里，系在腰部随身携带。把算筹装在袋子里或笔筒中随身携带，这就是古..._中国算筹
文章浏览阅读2k次。什么是JSON JSON（javascript object nanotion，js对象标记）是轻量级的数据交换格式，采用独立于语言的文本格式来存储和表示数据。JSON采用键值对保存数据，数据使用逗号分隔，花括号保存对象，方括号保存数组，键名使用双引号，键值间使用冒号分隔。如：{"name":[{"cnt":"张三","country":"中国"},{"cnt":"san zhan_jsonobject.parse(doposttojson);
文章浏览阅读4k次。卓老师，我有一个信号与系统的问题想请教。按照时域采样定理，采样频率≥2倍的信号频率，才能得到信号全部信息。而以智能车中的编码器测速为例。我们知道测速周期在可接受范围内越小越利于控速，比如2ms。但2ms采样一次速度，究竟能不能得到速度信号的全部信息我们却不得而知，归根结底是因为不知道速度信号的频率是多少。那么智能车速度信号的频率要如何得知呢？速度光电编码盘(回复)提问中的问题包括有三个子..._信号与系统最低采样频率
文章浏览阅读448次。前 言作为一名后台开发，对数据库进行基准测试，以掌握数据库的性能情况是非常必要的。本文介绍了MySQL基准测试的基本概念，以及使用sysbench对MySQL进行基准测试的详细方法。文章有疏漏之处，欢迎批评指正。一、基准测试简介1、什么是基准测试数据库的基准测试是对数据库的性能指标进行定量的、可复现的、可对比的测试。基准测试与压力测试基准测试可以理解为针对系统的一种压力测试。但基准测试不关心业务逻辑，更加简单、直接、易于测试，数据可以由工具生成，不要求真实；而压力测试一般考虑业务逻辑(如购物_sysbench mysql基准测试
文章浏览阅读5.2k次，点赞3次，收藏2次。音频一般是采用成PCM格式，而计算PCM格式音频尺寸，就需要如下几个参数。通道数，采样频率，采用格式。通道数：个人理解，就是同时有个几个设备在进行音频的采样，最少为1，一般通道数越多，音质越好。采样频率：（也称为采样速度或者采样频率）定义了每秒从连续信号中提取并组成离散信号的采样个数，它用赫兹（Hz）来表示。采用位数：既然采样频率表示每秒采样的个数，那么如何描述每个_av_samples_get_buffer_size
文章浏览阅读151次。上一篇文章介绍安装appium测试环境，这一片研究介绍如何测试Android自动化。上一篇地址：《【Mac + Appium学习(一)】之安装Appium环境》这一篇参考：《Mac 下 appium 自动化测试 Android 测试配置和脚本编写(四)》配置环境：Appium version ：1.9.1Appium-desktop：后改为1.7.1Android：6..._appium和appium-desktop哪个做自动化测试好