P3805 manacher 算法 学习笔记

【模板】manacher 算法 - 洛谷

题目描述

给出一个只由小写英文字符 \texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt za,b,c,…y,z 组成的字符串 SS ,求 SS 中最长回文串的长度 。

字符串长度为 nn。

输入格式

一行小写英文字符 \texttt a,\texttt b,\texttt c,\cdots,\texttt y,\texttt za,b,c,⋯,y,z 组成的字符串 SS。

输出格式

一个整数表示答案。

输入输出样例

输入 #1复制

aaa

输出 #1复制

3

说明/提示

1\le n\le 1.1\times 10^71≤n≤1.1×107。

题解：

        怎么说呢.......manacher我本来以为是很简单的算法，因为当时我就认为它实现的原理应该就是把求过的东西根据回文的性质来避免后来求的东西的重复计算。但是我看了一个小时的博客才找到能看懂的......那个博客有一句很精髓的话：

“如此一来，相比你差不多已经明白了manacher算法为何能够降低时间复杂度了。原因在于我是从左到右遍历，左边已经判断过的，右边又何必再判断一次呢？直接因为对称所以一样就完事了。（是不是很像求对称函数的单调性？）”

​​​​​​Manacher(马拉车)算法 清晰详解 代码分析 -查找字符串中所有回文子串_南波兔不写巴哥的博客-CSDN博客_manacher算法主要解决字符串的什么问题

简单思考：

我只是一个学算法的，就懒得写了QwQ。主要还是左往右暴力枚举每个点，然后尽量往两边暴力遍历找回文串。但是在暴力中有优化，维护一个r最右的点mid，之前找的回文串根据对称性，如果能用到关于mid对称的点的d长度，那就直接用了，然后再暴力往两边遍历；如果用不到，那只能暴力往两边遍历。

可以想想，如果有很多回文串，是不是不用怎么暴力，一直用之前的d就行了，接近O(n);

如果没什么回文串，那么暴力也不会跑几次，而且你暴力每跑一次，都会减少后面相应长度的暴力量，这么一想，好像也是O(n)的。

tql。

带板子：

/*keep on going and never give up*/#includeusing namespace std;#define int long long#define ll long long#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);inline int read(){    int x=0,k=1; char c=getchar();    while(c'9'){if(c=='-')k=-1;c=getchar();}    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();    return x*k;}const double E = exp(1);const double PI = acos(-1.0);const int mod=1e9+7; const int maxn=1e7+10;int n,ans,d[maxn<<1];int cnt=0,cnt2=0;char c;char str[maxn<<1];void change(){c=getchar();    str[0]='~',str[cnt=1]='|';    while(c'z') c=getchar();    while(c>='a'&&c<='z') str[++cnt]=c,str[++cnt]='|',c=getchar();}void manacher(){for(int r=0,mid,i=1;i<=cnt;i++){if(i<=r) d[i]=min(d[(mid<r) r=d[i]+i-1,mid=i;if(d[i]>ans) ans=d[i];}}signed main(){change();manacher();cout<<ans-1;}

ps：完结撒花！