当前位置: 首页 > news >正文

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 最长回文子串

方法&#xff1a;求字符串的 #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单片机开发:独立键盘实验

实验目的&#xff1a;按下键盘1时&#xff0c;点亮LED灯1。 键盘原理图如下图所示&#xff0c;可见&#xff0c;由于接GND&#xff0c;当键盘按下时&#xff0c;P3相应的端口为低电平。 键盘按下时会出现抖动&#xff0c;时间通常为5-10ms&#xff0c;代码中通过延时函数delay…...

组件框架漏洞

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

OFDM系统仿真

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

基于单片机的盲人智能水杯系统(论文+源码)

1 总体方案设计 本次基于单片机的盲人智能水杯设计&#xff0c;采用的是DS18B20实现杯中水温的检测&#xff0c;采用HX711及应力片实现杯中水里的检测&#xff0c;采用DS1302实现时钟计时功能&#xff0c;采用TTS语音模块实现语音播报的功能&#xff0c;并结合STC89C52单片机作…...

安心即美的生活方式

如果你的心是安定的&#xff0c;那么&#xff0c;外界也就安静了。就像陶渊明说的&#xff1a;心远地自偏。不是走到偏远无人的边荒才能得到片刻清净&#xff0c;不需要使用洪荒之力去挣脱生活的枷锁&#xff0c;这是陶渊明式的中国知识分子的雅量。如果你自己是好的男人或女人…...

安卓(android)订餐菜单【Android移动开发基础案例教程(第2版)黑马程序员】

一、实验目的&#xff08;如果代码有错漏&#xff0c;可查看源码&#xff09; 1.掌握Activity生命周的每个方法。 2.掌握Activity的创建、配置、启动和关闭。 3.掌握Intent和IntentFilter的使用。 4.掌握Activity之间的跳转方式、任务栈和四种启动模式。 5.掌握在Activity中添加…...

【cocos creator】【模拟经营】餐厅经营demo

下载&#xff1a;【cocos creator】模拟经营餐厅经营...

前端 | 深入理解Promise

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

Visual Studio Code修改terminal字体

个人博客地址&#xff1a;Visual Studio Code修改terminal字体 | 一张假钞的真实世界 默认打开中断后字体显示如下&#xff1a; 打开设置&#xff0c;搜索配置项terminal.integrated.fontFamily&#xff0c;修改配置为monospace。修改后效果如下&#xff1a;...

自然语言处理-词嵌入 (Word Embeddings)

人工智能例子汇总&#xff1a;AI常见的算法和例子-CSDN博客 词嵌入&#xff08;Word Embedding&#xff09;是一种将单词或短语映射到高维向量空间的技术&#xff0c;使其能够以数学方式表示单词之间的关系。词嵌入能够捕捉语义信息&#xff0c;使得相似的词在向量空间中具有…...

自定义数据集 使用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重建方法

众所周知&#xff0c;DUSt3R只适合做稀疏视角重建&#xff0c;与sapnn3r的目的类似&#xff0c;这篇文章以并行的方法&#xff0c;扩展了DUSt3R在多视图重建中的能力。 abstract 多视角三维重建仍然是计算机视觉领域的核心挑战&#xff0c;尤其是在需要跨不同视角实现精确且可…...

谈谈你所了解的AR技术吧!

深入探讨 AR 技术的原理与应用 在科技飞速发展的今天&#xff0c;AR&#xff08;增强现实&#xff09;技术已经悄然改变了我们与周围世界互动的方式。你是否曾想象过如何能够通过手机屏幕与虚拟物体进行实时互动&#xff1f;在这篇文章中&#xff0c;我们将深入探讨AR技术的原…...

upload labs靶场

upload labs靶场 注意:本人关卡后面似乎相比正常的关卡少了一关&#xff0c;所以每次关卡名字都是1才可以和正常关卡在同一关 一.个人信息 个人名称&#xff1a;张嘉玮 二.解题情况 三.解题过程 题目&#xff1a;up load labs靶场 pass 1前后端 思路及解题&#xff1a;…...

搜索引擎友好:设计快速收录的网站架构

本文来自&#xff1a;百万收录网 原文链接&#xff1a;https://www.baiwanshoulu.com/14.html 为了设计一个搜索引擎友好的网站架构&#xff0c;以实现快速收录&#xff0c;可以从以下几个方面入手&#xff1a; 一、清晰的目录结构与层级 合理划分内容&#xff1a;目录结构应…...

基于 oneM2M 标准的空气质量监测系统的互操作性

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

春晚舞台上的人形机器人:科技与文化的奇妙融合

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

零基础学习书生.浦语大模型-入门岛

第一关&#xff1a;Linux基础知识 Cursor连接服务器 使用Remote - SSH插件即可 注&#xff1a;46561&#xff1a;服务器端口号 运行指令 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 中&#xff0c;向 addConstr 这个方法中传入一个 TempConstr 对象&#xff0c;在模型中就会根据这个对象生成一个约束。更重要的是&#xff1a;TempConstr 对象可以传给所有addConstr系列方法&#xff0c;所以下面先介绍 TempConstr 对象 TempConstr TempC…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...