Manacher 最长回文子串
方法:求字符串的
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+9;
char s[N];
int p[N];int main()
{cin>>s+1;int n=strlen(s+1);s[0]='^';s[2*n+2]='$'; for(int i=2*n+1;i>=1;i--){s[i]=(i&1)?'#':s[i>>1];//右移表示除2 }int C=0,R=0;//C表示最长回文串的中心 //R表示最长回文串的回文半径for(int i=1;i<=2*n+1;i++){//半径初始化 p[i]=(i<R)?min(p[2*C-i],C-i):1;//暴力搜索while(s[i+p[i]]==s[i-p[i]])p[i]++;if(i+p[i]>R)C=i,R=i+p[i]; } int ans=0;for(int i=1;i<=2*n+1;i++) ans=max(ans,p[i]-1);cout<<ans<<endl;return 0;
}
转换之后的回文半径和转换之前的回文串长度的关系
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+9;
char s[N];
int p[N];int main()
{cin>>s+1;int n=strlen(s+1);s[0]='^';s[2*n+2]='$';//设置开头和结尾的哨兵for(int i=2*n+1;i>=1;i--){s[i]=(i&1)?'#':s[i>>1];//在原字符串中插入'#'号}int C=0,R=0;//C表示最长回文子串的中心位置,R表示当前for(int i=1;i<=2*n+1;i++){p[i]=i<R?min(R-i,p[2*C-i]):1;//判断i是否在盒子里//在的话就取对称半径和当前点到边界的最小值//不在的话就将半径设置为1while(s[i+p[i]]==s[i-p[i]])p[i]++;//然后开始暴力搜索,结果是当前点的最大回文半径if(i+p[i]>R) C=i,R=i+p[i];
//如果当前点的最大回文半径是最大的则更新为最大回文半径,
// 当前点更新为新的中心}int ans=0;for(int i=1;i<=2*n+1;i++){ans=max(ans,p[i]-1);}// 转换之后最长回文半径-1 = 转换之前最长回文子串的长度。cout<<ans<<endl;return 0;
}
最长回文子串
相关文章:

Manacher 最长回文子串
方法:求字符串的 #include<bits/stdc.h> using namespace std; using lllong long; const int N1e69; char s[N]; int p[N];int main() {cin>>s1;int nstrlen(s1);s[0]^;s[2*n2]$; for(int i2*n1;i>1;i--){s[i](i&1)?#:s[i>>1];//右移表示…...

51单片机开发:独立键盘实验
实验目的:按下键盘1时,点亮LED灯1。 键盘原理图如下图所示,可见,由于接GND,当键盘按下时,P3相应的端口为低电平。 键盘按下时会出现抖动,时间通常为5-10ms,代码中通过延时函数delay…...

组件框架漏洞
一.基础概念 1.组件 定义:组件是软件开发中具有特定功能或特性的可重用部件或模块,能独立使用或集成到更大系统。 类型 前端 UI 组件:像按钮、下拉菜单、导航栏等,负责构建用户界面,提升用户交互体验。例如在电商 AP…...

OFDM系统仿真
1️⃣ OFDM的原理 1.1 介绍 OFDM是一种多载波调制技术,将输入数据分配到多个子载波上,每个子载波上可以独立使用 QAM、PSK 等传统调制技术进行调制。这些子载波之间互相正交,从而可以有效利用频谱并减少干扰。 1.2 OFDM的核心 多载波调制…...

基于单片机的盲人智能水杯系统(论文+源码)
1 总体方案设计 本次基于单片机的盲人智能水杯设计,采用的是DS18B20实现杯中水温的检测,采用HX711及应力片实现杯中水里的检测,采用DS1302实现时钟计时功能,采用TTS语音模块实现语音播报的功能,并结合STC89C52单片机作…...
安心即美的生活方式
如果你的心是安定的,那么,外界也就安静了。就像陶渊明说的:心远地自偏。不是走到偏远无人的边荒才能得到片刻清净,不需要使用洪荒之力去挣脱生活的枷锁,这是陶渊明式的中国知识分子的雅量。如果你自己是好的男人或女人…...

安卓(android)订餐菜单【Android移动开发基础案例教程(第2版)黑马程序员】
一、实验目的(如果代码有错漏,可查看源码) 1.掌握Activity生命周的每个方法。 2.掌握Activity的创建、配置、启动和关闭。 3.掌握Intent和IntentFilter的使用。 4.掌握Activity之间的跳转方式、任务栈和四种启动模式。 5.掌握在Activity中添加…...

【cocos creator】【模拟经营】餐厅经营demo
下载:【cocos creator】模拟经营餐厅经营...

前端 | 深入理解Promise
1. 引言 JavaScript 是一种单线程语言,这意味着它一次仅能执行一个任务。为了处理异步操作,JavaScript 提供了回调函数,但是随着项目处理并发任务的增加,回调地狱 (Callback Hell) 使异步代码很难维护。为此,ES6带来了…...

Visual Studio Code修改terminal字体
个人博客地址:Visual Studio Code修改terminal字体 | 一张假钞的真实世界 默认打开中断后字体显示如下: 打开设置,搜索配置项terminal.integrated.fontFamily,修改配置为monospace。修改后效果如下:...
自然语言处理-词嵌入 (Word Embeddings)
人工智能例子汇总:AI常见的算法和例子-CSDN博客 词嵌入(Word Embedding)是一种将单词或短语映射到高维向量空间的技术,使其能够以数学方式表示单词之间的关系。词嵌入能够捕捉语义信息,使得相似的词在向量空间中具有…...

自定义数据集 使用pytorch框架实现逻辑回归并保存模型,然后保存模型后再加载模型进行预测,对预测结果计算精确度和召回率及F1分数
import numpy as np import torch import torch.nn as nn import torch.optim as optim from sklearn.metrics import precision_score, recall_score, f1_score# 数据准备 class1_points np.array([[1.9, 1.2],[1.5, 2.1],[1.9, 0.5],[1.5, 0.9],[0.9, 1.2],[1.1, 1.7],[1.4,…...

【论文笔记】Fast3R:前向并行muti-view重建方法
众所周知,DUSt3R只适合做稀疏视角重建,与sapnn3r的目的类似,这篇文章以并行的方法,扩展了DUSt3R在多视图重建中的能力。 abstract 多视角三维重建仍然是计算机视觉领域的核心挑战,尤其是在需要跨不同视角实现精确且可…...
谈谈你所了解的AR技术吧!
深入探讨 AR 技术的原理与应用 在科技飞速发展的今天,AR(增强现实)技术已经悄然改变了我们与周围世界互动的方式。你是否曾想象过如何能够通过手机屏幕与虚拟物体进行实时互动?在这篇文章中,我们将深入探讨AR技术的原…...

upload labs靶场
upload labs靶场 注意:本人关卡后面似乎相比正常的关卡少了一关,所以每次关卡名字都是1才可以和正常关卡在同一关 一.个人信息 个人名称:张嘉玮 二.解题情况 三.解题过程 题目:up load labs靶场 pass 1前后端 思路及解题:…...
搜索引擎友好:设计快速收录的网站架构
本文来自:百万收录网 原文链接:https://www.baiwanshoulu.com/14.html 为了设计一个搜索引擎友好的网站架构,以实现快速收录,可以从以下几个方面入手: 一、清晰的目录结构与层级 合理划分内容:目录结构应…...

基于 oneM2M 标准的空气质量监测系统的互操作性
论文标题 英文标题: Interoperability of Air Quality Monitoring Systems through the oneM2M Standard 中文标题: 基于 oneM2M 标准的空气质量监测系统的互操作性 作者信息 Jonnar Danielle Diosana, Gabriel Angelo Limlingan, Danielle Bryan Sor…...

春晚舞台上的人形机器人:科技与文化的奇妙融合
文章目录 人形机器人Unitree H1的“硬核”实力传统文化与现代科技的创新融合网友热议与文化共鸣未来展望:科技与文化的更多可能结语 2025 年央视春晚的舞台,无疑是全球华人目光聚焦的焦点。就在这个盛大的舞台上,一场名为《秧BOT》的创意融合…...

零基础学习书生.浦语大模型-入门岛
第一关:Linux基础知识 Cursor连接服务器 使用Remote - SSH插件即可 注:46561:服务器端口号 运行指令 python hello_world.py端口映射 ssh -p 46561 rootssh.intern-ai.org.cn -CNg -L 7860:127.0.0.1:7860 -o StrictHostKeyCheckingno …...
Gurobi基础语法之 addConstr, addConstrs, addQConstr, addMQConstr
在新版本的 Gurobi 中,向 addConstr 这个方法中传入一个 TempConstr 对象,在模型中就会根据这个对象生成一个约束。更重要的是:TempConstr 对象可以传给所有addConstr系列方法,所以下面先介绍 TempConstr 对象 TempConstr TempC…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...

IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...