定义与基本求法
-
定义
又名 马拉车 ，用于处理子串回文问题。
-
基本求法
暴力判断每个子串是否是回文是 \(O(n^3)\) 的，根据其对称性优化为 \(O(n^2)\) 依旧是不优秀的。
马拉车便是解决这种单一问题的算法，具有局限性，但同时是解决这种问题的不二选择。
枚举回文串的中点，例如 \(aabaa\) 的中点为 \(b\) ，依次为基础进行下一步判断。
那么这里发现如果回文串长度为偶数则无法判断，于是将其进行下述优化：
例如 \(aaaaaa\) ，将其每一个空隙插入一个 \(\#\) （两边也插）：\(\#a\#a\#a\#a\#a\#a\#\) ，这样其中点就变成了 \(\#\) ，长度也变为奇数。同时为了方便，对于奇数长度的回文也不放过，如 \(aaa→\#a\#a\#a\#\) ，每一个长度为 \(n\) 的回文长度都变为 \(2\times n+1\) ，这样无一例外的全部变为奇数长度。
先设 \(p_i\) 为以 \(i\) 为中点的回文的最长半径，例如：\(\#a\#a\#a\#a\#\) ，以中间的 \(\#\) 为中点，则其最长半径为 \(4\) ，即 \(\#a\#a\#\) 的长度。
再以 \(i\) 为中心，不断向两边扩张。定义 \(mx\) 为之前找到的回文串最靠右的右边界，\(id\) 表示这个最大右边界对称轴的位置。
那么 $i $ 在 \(mx\) 以内时，显然时存在对称性的，\(p_i=p_{id\times 2-j}\) ，前提是其右端点必须在 \(mx\) 以内，否则其右端点只能到 \(mx\) , \(p_i\) 也只能 \(=mx-i\) 。继续向外扩展
不然他就只能自力更生了，\(p_j=0\) ，再进一步向外扩展。
只要 \(s[i+p_i]=s[i-p_i]\) 就说明可以继续向外扩展了，\(p_i++\) 。
那么在扩展的过程中，超出 \(mx\) 了，就刷新 \(mx\) 的值，同时 \(i\) 也成了新的 \(id\) 。
其实把马拉车理解了会发现这个东西很简单，很好理解，没有那么抽象。
于是就通过上述方法求出了每一个 \(p_i\) 。
参考下面一些图：
综上所述：
int init() { int len=strlen(str); s[0]='@',s[1]='#'; int j=2; for(int i=0;i<len;i++) s[j++]=str[i],s[j++]='#'; s[j]='\0'; return j; } void manacher() { int ans=-1,mx=0,id=0,len=init(); for(int i=1;i<len;i++) { if(i<mx) p[i]=min(p[id*2-i],mx-i); else p[i]=1; while(s[i+p[i]]==s[i-p[i]]) p[i]++; if(p[i]+i>mx) mx=p[i]+i,id=i; } }
例题
模板
- 题目链接
- 上面的代码找最大的 \(p_i-1\) 即可。（因为 \(\#\) ）
神奇项链
-
题面：
多个回文串拼在一起，且相同部分可重叠，如 \(aba,aca\) 可以拼成 \(abaaca\) 或 \(abaca\) ，给定一字符串 \(s\) ，求拼成该字符串最少需要多少步。
-
解法：
我们是将每个串插上 \(\#\) 的，所以就算不另其重叠，\(\#\) 也是会重叠的，这就解决了判断重叠的问题。
那么对于其每次拼定会存在重叠，所以只要求其最少产生多少重叠即可。
那么用到马拉车，先求出每个 \(p_i\) ，随后就可以求出每一个回文的左右端点，将这些端点以左端点前后顺序排序。
这样使每两个回文重叠部分尽可能的小。确定一回文 \(s\) 的右端点（当然也是尽可能靠右的，即当前左端点允许的，右端点最靠后的回文右端点），枚举后面回文的左端点，使其右端点端点尽可能的靠后，直至左端点与 \(s\) 右端点重合，在此过程中，刷新最靠后的右端点。
举个例子，方便理解：
有次可见上述文字描述的正确性，以及无论拼合时无论是否重叠，加上 \(\#\) 之后都是有重叠的。
-
代码如下：
#include<bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int N=1e6+10,P=1e9+7; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=1; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } char str[N],s[N]; int p[N],len; struct aa { int sta,en; }a[N]; bool cmp(aa a,aa b) {return a.sta<b.sta;} int init() { int len=strlen(str); s[0]='#'; int j=1; for(int i=0;i<len;i++) s[j++]=str[i],s[j++]='#'; s[j]='\0'; return j; } void manacher() { int ans=-1,mx=0,id=0,len=init(); for(int i=0;i<len;i++) { if(i<mx) p[i]=min(p[id*2-i],mx-i); else p[i]=1; while(s[i+p[i]]==s[i-p[i]]) p[i]++; if(p[i]+i>mx) mx=p[i]+i,id=i; } } int cover() { int len=init(); for(int i=0;i<len;i++) a[i].sta=i-p[i]+1, a[i].en=i+p[i]-1; stable_sort(a,a+len,cmp); int far=0,ans=0,i=0; for(i=0;a[i].sta<=0;i++) if(a[i].en>a[far].en) far=i; while(i<len) { ans++; int x=far; while(a[i].sta<=a[far].en&&i<len) { i++; if(a[i].en>a[x].en) x=i; } far=x; } return ans; } signed main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif while(scanf("%s",str)!=EOF) { memset(p,0,sizeof(p)); memset(a,0,sizeof(a)); manacher(); cout<<cover()-1<<endl; } } -
由此可见，马拉车也可以作为求具体问题的辅助算法存在。
总结
作为一个相对简单且应用范围不广的算法，没有找到别的经典例题了，到这儿就结束了。
打完博客对于其理解还是有很大进步的。
再次吐槽一下网课质量，依旧是网上找资料进行学习的。
例题的图是自己画的，上面基本求法的图是网上找的，感觉不错就扣下来了。
神奇项链这题感觉也是挺不错的，教练得知 \(oj\) 上没有马拉车刚刚加上的，别的网站上没找到这道题（主要洛谷被禁了）,感觉应该是道蓝。
标签：重叠,int,manacher,笔记,id,学习,端点,mx,回文 From： https://www.cnblogs.com/Charlieljk/p/17997893