首页 > 编程语言 >马拉车算法

马拉车算法

时间:2023-06-13 22:57:59浏览次数:33  
标签:const int char 算法 maxn include 拉车

截图来自董老师https://www.bilibili.com/video/BV173411V7Ai/?spm_id_from=333.999.0.0&vd_source=23dc8e19d485a6ac47f03f6520fb15c2

  P3805 【模板】manacher 算法

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=3e7+10;
const int INF=0x3fffffff;
typedef long long LL;

char a[maxn],s[maxn];
int d[maxn];
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+l],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);
    int k=0;
    s[0]='$';
    s[++k]='#';
    for(int i=1;i<=n;i++){
    	s[++k]=a[i];s[++k]='#';
	}
	n=k;
	get_d(s,n);
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,d[i]);
	printf("%d",ans-1);
return 0;
}

 

 

标签:const,int,char,算法,maxn,include,拉车
From: https://www.cnblogs.com/shirlybaby/p/17478908.html

相关文章

  • 【VRP问题】基于遗传算法求解多约束多无人机灾情应急救援路径规划问题附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 多种智能优化算法运行时间和不同函数测试对比附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 《数据结构与算法》之二叉树(补充树)
    一.树结构之二叉树操作二叉树的查找二叉搜索树,也称二叉排序树或二叉查找树二叉搜索树:一棵二叉树,可以为空,如果不为空,应该满足以下性质:非空左子树的所有结点小于其根结点的键值非空右子树的所有结点大于其根结点的键值左右子树都是二叉搜索树对于二叉树的查找,其实沿用的是......
  • 文心一言 VS 讯飞星火 VS chatgpt (40)-- 算法导论5.4 4题
    四、一次聚会需要邀请多少人,才能让其中3人的生日很可能相同?文心一言:为了解决这个问题,我们需要先计算出所有可能的生日组合数,然后计算出其中生日相同的组合数。已知需要邀请的人数为:23人根据组合数公式,可计算出所有可能的生日组合数:2.58520167*10^{22}根据生日相同的组合......
  • 文心一言 VS 讯飞星火 VS chatgpt (40)-- 算法导论5.4 4题
    四、一次聚会需要邀请多少人,才能让其中3人的生日很可能相同?文心一言:为了解决这个问题,我们需要先计算出所有可能的生日组合数,然后计算出其中生日相同的组合数。已知需要邀请的人数为:23人根据组合数公式,可计算出所有可能的生日组合数:2.58520167*10^{22}根据生日相同的组合数公式,可......
  • .NET编译项目时出现《此实现不是 Windows 平台 FIPS 验证的加密算法的一部分》处理方
    此实现不是Windows平台FIPS验证的加密算法的一部分。”)的问题,如下图所示:对于上面的问题,只需要修改下注册表即可处理,方法如下:1、以管理员方式启动命令行工具后输入regedit,回车打开注册器;。2、打开注册表后,进入路径:HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Co......
  • java常见的排序算法(冒泡排序、选择排序、插入排序、shell排序、归并排序、堆排序、快
    (文章目录)本文简单的介绍了java常见的几种排序。所有的排序均是一个数组由小到大进行排序。一、冒泡排序1、效率表现和适用范围效率O(n²)适用于排序小列表2、算法实现publicvoidbubbleSortArray(int[]a){ intn=a.length; for(inti=1;i<n;i++){ fo......
  • c#排序算法
    1.没有一种排序算法是万能的最快算法,因为最快的排序算法取决于数据的性质和排序要求。然而,对于一般情况下的排序问题,以下算法通常被认为是最快的:快速排序(QuickSort):这是一种基于分治思想的常见排序算法。其平均时间复杂度为O(nlogn)。因为其平均情况下时间复杂度相对较快,加上......
  • 字符串哈希算法
    问题描述考虑1044.最长重复子串(Hard),本题思路并不难,可以使用二分答案来解决,假设答案为mid,那么长度大于mid的子串在s中只会出现一次,否则至少出现两次。因此只需要考虑子串在s中的出现次数即可,比较直接的想法是使用key为string的unordered_map,然而unoredere_map......
  • 快速选择算法
    问题描述给定一个长度为$n$的数组,如何在$O(n)$的时间复杂度内找到第$k$大的数。思路朴素的想法是先排序,然后直接找到第$k$个元素,时间复杂度为$O(n\logn)$。我们可以利用快速排序的思想来解决这个问题,考虑快速排序的划分过程,在快速排序的“划分”结束后,数组$A_p\cdotsA_r$被......