当前位置: 首页 > 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…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

基础测试工具使用经验

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

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...