个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
25
4
manacher马拉车 https://www.luogu.com.cn/problem/P3805 。
闲言一下：花了一个中午终于把 manacher 给搞懂了。本文将以一个蒟蒻的身份来，来写写马拉车算法。首先请自行回顾暴力的 最长回文字符串 算法。首先我们将 通过枚举中心点，并扩展以该中心点为回文中心的回文串长度的算法称为 “中心扩展法”。manacher算法便是以“中心扩展法”为核心，利用枚举中获取的信息优化而来的.
具体地来说:
首先在解决奇偶回文字符串时，我们使用分类讨论的方法，解决了奇数和偶数的问题，但是这样未免过于麻烦，有什么可以将二者统一的方式呢?
这是处理前的字符串
具体地来说:
首先在解决奇偶回文字符串时，我们使用分类讨论的方法，解决了奇数和偶数的问题，但是这样未免过于麻烦，有什么可以将二者统一的方式呢?
这是处理前的字符串
a b b c
1 2 3 4
这是处理后的字符串
# a # b # b # c #
1 2 3 4 5 6 7 8 9
我们通过加字符的方法，注意这里不一定要是 # ，也可以是其他字符，主要目标是为了将奇偶回文字符串统一了起来。这样在处理回文字符串时，会更加的方便。（不过也容易犯一些粗心的小问题，这些问题会在文章末尾提及）.
接下来回想一下 中心扩展法 求解最长回文序列的时候。遇到这种情况时 。
a b a d a b a
1 2 3 4 5 6 7
当我们枚举完 以下标为 4 的点为中心时，我们可以知道 1~7 为回文序列。加上前面以下标为3的点为中心时，我们可知道 1~3 为回文序列。根据回文序列的对称性，我们可以得出 5~7 也为回文序列。但在我们使用中心扩展法时，就需要多余地去枚举以下标为3的点为中心的回文半径的长度。这大大地浪费了时间。因此我们可以从这个角度入手，优化我们的算法.
从 中心扩展法 的基础上，再根据刚刚从特殊数据的角度，我们可以想到先定义几个变量maxr,mid ，用来表示当前已知的回文序列中最右的右端点，及该回文序列的中点。为什么要记录最右的右端点呢？因为右端点越右的回文序列就越容易包括后面还未遍历的中心，这样就能尽可能的达到，通过现有信息尽可能减少多余遍历的目的了。再定义一个数组 p[i] 表示以 i 为中点的回文序列的回文半径.
具体来讲一下优化的要点， 。
情况一 。
a b b c
1 2 3 4
这是处理后的字符串
# a # b # b # c #
1 2 3 4 5 6 7 8 9
我们通过加字符的方法，注意这里不一定要是 # ，也可以是其他字符，主要目标是为了将奇偶回文字符串统一了起来。这样在处理回文字符串时，会更加的方便。（不过也容易犯一些粗心的小问题，这些问题会在文章末尾提及）.
接下来回想一下 中心扩展法 求解最长回文序列的时候。遇到这种情况时 。
a b a d a b a
1 2 3 4 5 6 7
当我们枚举完 以下标为 4 的点为中心时，我们可以知道 1~7 为回文序列。加上前面以下标为3的点为中心时，我们可知道 1~3 为回文序列。根据回文序列的对称性，我们可以得出 5~7 也为回文序列。但在我们使用中心扩展法时，就需要多余地去枚举以下标为3的点为中心的回文半径的长度。这大大地浪费了时间。因此我们可以从这个角度入手，优化我们的算法.
从 中心扩展法 的基础上，再根据刚刚从特殊数据的角度，我们可以想到先定义几个变量maxr,mid ，用来表示当前已知的回文序列中最右的右端点，及该回文序列的中点。为什么要记录最右的右端点呢？因为右端点越右的回文序列就越容易包括后面还未遍历的中心，这样就能尽可能的达到，通过现有信息尽可能减少多余遍历的目的了。再定义一个数组 p[i] 表示以 i 为中点的回文序列的回文半径.
具体来讲一下优化的要点， 。
情况一 。
。
如果是上图的这种情况，则p[i]=p[j] ， j=mid-(i-mid) --> j=2*mid-i 。（回文序列的对称性） 。
情况二 。
。
如果是上图的这种情况，则不一定p[i]=p[j] ，因为超过ml ~ mr的部分并不满足回文序列的性质。所以只有在ml ~ mr的部分才能进入计算，因此p[i]=mr-i+1 .
重要的优化只有这些，其他的和 中心扩展法的做法大致相同.
#include<bits/stdc++.h>
using
namespace
std;
const
int
N=
9
*
1e7;
string
str=
"
!#
"
,c;
/*
为什么第一位是“！”？
为了避免程序第16行扩展时越界
*/
int
p[N],mid=
0
,mr=
0
,ans;
void
work(){
cin
>>
c;
for
(
int
i=
0
;c[i]>=
'
a
'
&&c[i]<=
'
z
'
;i++
){
str
+=
c[i];
str
+=
'
#
'
;
}
/*
处理原序列
*/
for
(
int
i=
1
;i<str.size();i++
){
if
(i<=mr) p[i]=min(p[
2
*mid-i],mr-i+
1
);
/*
i关于mid对称点; mid-（i-mid）——> 2*mid-i
*/
while
(str[i-p[i]]==str[i+p[i]]) p[i]++
;
//
这里其实就是扩展 回文序列的 回文半径
if
(i+p[i]>
mr){
mid
=
i;
mr
=i+p[i]-
1
;
}
if
(p[i]>ans) ans=
p[i];
}
cout
<<ans-
1
;
}
int
main(){
work();
return
0
;
}
。
粗心的小问题（建议自行写完代码后查看） 。
1.因为要插入一堆字符，所以字符数组和其他相关数组的大小需要翻倍 。
最后此篇关于[最长回文字符串]manacher马拉车的文章就讲到这里了,如果你想了解更多关于[最长回文字符串]manacher马拉车的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
25
4
0
我最近阅读了一篇关于 Manacher 算法的维基百科文章，在看到示例实现和许多其他实现之后......老实说，我不知道这个算法是如何线性的。在我看来，最好的情况是 O(n+n/2)，但这不是线性的，
在尝试消化 Manacher 的算法大约 6-8 小时后，我准备认输。但在我这样做之前，这是黑暗中的最后一枪:谁能解释一下？我不关心代码。我希望有人解释一下算法。 这里似乎是其他人在解释算法时喜欢的地
我正在学习 Manacher 算法来解决最长回文子串问题，我知道它利用了这样一个事实，即如果 i' 是回文的中心，那么就会有一个以 i 为中心的回文。 我们不是从零开始扩展，而是维护一个数组 P 来跟
我是一名优秀的程序员,十分优秀！