字符串(算法竞赛)--Manacher(马拉车)算法

1、B站视频链接:F05 Manacher(马拉车)_哔哩哔哩_bilibili

题目链接:【模板】manacher - 洛谷

​
#include <bits/stdc++.h>
using namespace std;
const int N=3e7;
char a[N],s[N];
int d[N];//回文半径函数void get_d(char*s,int n){d[1]=1;for(int i=2,l,r=1;i<=n;i++){if(i<=r)d[i]=min(d[r-i+1],r-i+1);//盒内加速while(s[i-d[i]]==s[i+d[i]])d[i]++;//盒外暴力枚举if(i+d[i]-1>r)l=i-d[i]+1,r=i+d[i]-1;//更新盒子 }
}
int main(){//改造串 scanf("%s",a+1);int n=strlen(a+1),k=0;s[0]='$',s[++k]='#';//0为$,1为#for(int i=1;i<=n;i++){s[++k]=a[i],s[++k]='#';}n=k;//最后的长度为kget_d(s,n);int ans=0;for(int i=1;i<=n;i++){ans=max(ans,d[i]);}printf("%d\n",ans-1);//最大半径减一 return 0;
} ​

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/263365.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

线段树学习笔记 下

可持久化线段树 上面两篇是几年前写的&#xff0c;笔者今日才加以整理&#xff0c;如有错误请见谅。 线段树加上版本就是可持久化线段树。 Problem Intro 给定一个数组&#xff0c;只需要单点修改和单点查询&#xff0c;但要维护版本。 具体说&#xff0c;每一次操作可能从…

五、分类算法 总结

代码&#xff1a; from sklearn.datasets import load_iris, fetch_20newsgroups from sklearn.feature_extraction.text import TfidfVectorizer from sklearn.model_selection import train_test_split, GridSearchCV from sklearn.naive_bayes import MultinomialNB from s…

Stable Diffusion 模型的概念、类型、下载、安装、使用

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里。 大家好&#xff0c;我是水滴~~ 我们在《Stable Diffusion WebUI 界面介绍》 时&#xff0c;第一个就讲到了 Stable Diffusion 模型&#xff0c;那么这个模型是什么&#xff1f;该从哪儿下载&…

东方博宜 1519. 求1~n中每个数的因子有哪些?

东方博宜 1519. 求1~n中每个数的因子有哪些&#xff1f; #include<iostream> using namespace std; int main() {int n ;cin >> n ;for(int i 1 ; i < n ; i){int a[1000] ;int k 0 ;for(int j 1 ; j < i ; j){if(i%j0){a[k] j ;k ;} }cout << i …

前端工程化面试题 | 17.精选前端工程化高频面试题

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

JVM(1)

JVM简介 JVM是Java Virtual Machine的简称,意为Java虚拟机. 在java中,它归属于jre(java运行时环境), 而jre归属于jdk(java开发工具包). 虚拟机是指通过软件模拟的具有完整硬件功能的,运行在一个完全隔离的环境中的完整计算机系统. 常见的虚拟机:JVM, VMwave, VirtualBox. J…

Spring Security学习(七)——父子AuthenticationManager(ProviderManager)

前言 《Spring Security学习&#xff08;六&#xff09;——配置多个Provider》有个很奇怪的现象&#xff0c;如果我们不添加DaoAuthenticationProvider到HttpSecurity中&#xff0c;似乎也能够达到类似的效果。那我们为什么要多此一举呢&#xff1f;从文章的效果来看确实是多…

AI:135-基于卷积神经网络的艺术品瑕疵检测与修复

🚀点击这里跳转到本专栏,可查阅专栏顶置最新的指南宝典~ 🎉🎊🎉 你的技术旅程将在这里启航! 从基础到实践,深入学习。无论你是初学者还是经验丰富的老手,对于本专栏案例和项目实践都有参考学习意义。 ✨✨✨ 每一个案例都附带关键代码,详细讲解供大家学习,希望…

Mybatis总结--传参二

#叫做占位符 Mybatis是封装的JDBC 增强版 内部还是用的jdbc 每遇到一个#号 这里就会变为&#xff1f;占位符 一个#{}就是对应一个问号 一个占位符 用这个对象执行sql语句没有sql注入的风险 八、多个参数-使用Param 当 Dao 接口方法有多个参数&#xff0c;需要通过名称使…

力扣随笔之颜色分类(中等75)

思路&#xff1a;定义两个指针划分left&#xff0c;right划分三个区域left左边是红色区域&#xff0c;right右边是蓝色区域&#xff0c;left和right之间是白色区域&#xff1b;定义一个遍历指针遍历整个数组&#xff0c;遇到红色与left所指位置数字交换&#xff0c;并将left自加…

Element table 实现表格行、列拖拽功能

安装包 npm install sortablejs --save <template><div class"draggable" style"padding: 20px"><el-table row-key"id" :data"tableData" style"width: 100%" border><el-table-columnv-for"(it…

趣学贝叶斯统计:贝叶斯定理和乐高积木

利用贝叶斯定理&#xff0c;可以将条件概率倒置。知道P(B|A)&#xff0c;就可以求出P(A|B)。例如&#xff0c;知道感冒时你打喷嚏的概率&#xff0c;就可以倒过来判断打喷嚏时你感冒的概率。这样&#xff0c;我们就用数据更新了自己对世界的信念。 目录 1. 运用乐高2. 通过数学…

SpringBoot和SpringCloud的区别,使用微服务的好处和缺点

SpringBoot是一个用于快速开发单个Spring应用程序的框架&#xff0c;通过提供默认配置和约定大于配置的方式&#xff0c;快速搭建基于Spring的应用。让程序员更专注于业务逻辑的编写&#xff0c;不需要过多关注配置细节。可以看成是一种快速搭建房子的工具包&#xff0c;不用从…

C语言:指针的进阶讲解

目录 1. 二级指针 1.1 二级指针是什么&#xff1f; 1.2 二级指针的作用 2. 一维数组和二维数组的本质 3. 指针数组 4. 数组指针 5. 函数指针 6. typedef的使用 7. 函数指针数组 7.1 转移表 1. 二级指针 如果了解了一级指针&#xff0c;那二级指针也是可以很好的理解…

【安卓逆向】app防止截屏分析与去除

本次分析的app name为&#xff1a;5paH5qGI54uX 这款应用打开之后里面的内容是不允许截图的&#xff0c;防止截图分析&#xff1a;Android应用防止截屏_landroid/view/window;->setflags 0x2000-CSDN博客 App防止恶意截屏功能的方法&#xff1a;iOS、Android和鸿蒙系统的实…

红日靶场3

靶场链接&#xff1a;漏洞详情 在虚拟机的网络编辑器中添加两个仅主机网卡 信息搜集 端口扫描 外网机处于网端192.168.1.0/24中&#xff0c;扫描外网IP端口&#xff0c;开放了80 22 3306端口 80端口http服务&#xff0c;可以尝试登录网页 3306端口mysql服务&#xff0c;可…

7-liunx服务器规范

目录 概况liunx日志liunx系统日志syslog函数openlog 可以改变syslog默认输出方式 &#xff0c;进一步结构化 用户信息进程间的关系会话ps命令查看进程关系 系统资源限制改变工作目录和根目录服务器程序后台话 概况 liunx服务器上有很多细节需要注意 &#xff0c;这些细节很重要…

nodejs+vue+ElementUi废品废弃资源回收系统

系统主要是以后台管理员管理为主。管理员需要先登录系统然后才可以使用本系统&#xff0c;管理员可以对系统用户管理、用户信息管理、回收站点管理、站点分类管理、站点分类管理、留言板管理、系统管理进行添加、查询、修改、删除&#xff0c;以保障废弃资源回收系统系统的正常…

瑞_23种设计模式_装饰者模式

文章目录 1 装饰者模式&#xff08;Decorator Pattern&#xff09;1.1 介绍1.2 概述1.3 装饰者模式的结构 2 案例一2.1 需求2.2 代码实现 3 案例二3.1 需求3.2 代码实现 4 JDK源码解析5 总结5.1 装饰者模式的优缺点5.2 装饰者模式的使用场景5.3 装饰者模式 VS 代理模式 &#x…

创作纪念日:记录我的成长与收获

机缘 一开始是在我深入学习前端知识的Vue.js框架遇到了一个问题&#xff0c;怎么都解决不了&#xff0c;心烦意乱地来csdn上找解决方法。开心的是真被我找到了&#xff0c;真的很感恩&#xff0c;也意识到在这个平台上分享自己的经验是多么有意义的事情&#xff0c;可能随便的…