【OI之路】10字符串-2Manacher

一句精辟的话:字符串相关算法就是用来偷懒的——scy
更详细地解释:Manacher、莫队、fft、后缀数组、exkmp等各种算法,本质上都是尽量地利用子信息、残留信息

一、定义

应用:求最长回文子串。
暴力复杂度:O(n^3)
Manacher复杂度:O(n)
是不是特别优越?

二、过渡算法

考虑枚举每一个中间点,向两边拓展,此时即O(n^2)
这种做法已经比暴力好很多了,但是让我们思考一些缺陷来提升效率。

1. 中间点的多样性

目前的做法,中间点有可能是字符(回文串长度为奇数)也可能是字符间的空隙(回文串长度为偶数),比较麻烦。考虑将空隙变成‘#’等绝对不出现字符,复杂度不变,但便于我们处理。
此时空隙数为字符数+1

2. 求解过程没有利用残留信息(这从来都是算法设计的关键)

  1. 通常我们要求的或者做题需要的辅助只是长度,与具体字符串无关,或许可以从这里入手。
  2. 所谓长度,而且还是回文的,我们可以定义【回文半径】,即回文串长度的一半,此后只需要考虑半径就等同于考虑长度。而且因为之前我们把空隙变成了字符,现在算出来的最大【回文半径-1】就是原来的回文串长度(因为空隙数必然是字符数+1)
    举例:
    1
    2
    3
    char: # a # b # b # a #
    RL : 1 2 1 2 5 2 1 2 1
    RL-1: 0 1 0 1 4 1 0 1 0

然后定义:
rx:当前所有回文子串最右触及位置
ma:回文半径数组

二、具体操作

接下来就是分类讨论i与rx的位置关系啦,因为这关系到状态的继承

(pos是rx的对应中介点,lx是对于左端点)

1. i<=rx

那么找到i关于pos对称的j
①ma[i]=ma[j]

②ma[i]=rx-i+1

2. i>rx

ma[i]=1

当然,这些继承只是基础,接下来还是要暴力拓展
这些主要是缩短了前面无意义的继承。

三、例题代码

2009 Multi-University Training Contest 16 - Host by NIT
Hdu3068
Caioj1179

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=110000;
const char SPC='#';
//*******************全局定义*******************
char s2[MAXN*2];
//*******************实现*******************
char s[MAXN*2];
int ma[MAXN*2];
int manacher()
{
int ln=strlen(s2+1);
for(int i=1;i<=ln;i++) s[2*i-1]=SPC,s[2*i]=s2[i];
ln=ln*2+1;s[ln]=SPC;
int md,rx=0,ans=0;
for(int i=1;i<=ln;i++)
{
if(i<=rx)
{
int j=2*md-i;
if(i+ma[j]-1<=rx) ma[i]=ma[j];
else ma[i]=rx-i+1;
}
else ma[i]=1;
while(i-ma[i]>=1 and i+ma[i]<=ln and s[i-ma[i]]==s[i+ma[i]]) ma[i]++;
if(rx<i+ma[i]-1) rx=i+ma[i]-1,md=i;
chmax(ans,ma[i]-1);
}
return ans;
}
//*******************主函数*******************
int main()
{
//freopen("tmp.in","r",stdin);
while(scanf("%s",s2+1)!=EOF) printf("%d\n",manacher());
}

参考文献:

segmentfault-曾会玩
刘毅

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/1c35.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%