更新日志
2025/01/22：开工。
思路
马拉车算法用于解决回文子串问题，思路类似于Z函数。
首先我们考虑使所有回文串都是奇数串，具体的，我们在两两字符之间插入相同的特殊字符，比如：
\[\texttt{abcba}\rightarrow\texttt{\#a\#b\#c\#b\#a\#} \]不难发现此时所有回文串串长均为奇数。
类似地，我们考虑 \(p_i\) 表示 \(i\) 为中心最长回文串的半长，储存最大的 \(i+p_i-1\)（我令 \(p_i\) 包含中心字符），将这段半长的左右端点记作 \(l,r\)。
首先，一个位置 \(i\) 的对应位置为 \(j=2l-i\)，简单推式子。
若 \(p_j\) 不超过整个红框的左边界，由于整个红框都是回文串，那么 \(p_i=p_j\)。
否则，我们暴力向外扩展即可。
细节
更改字符串，如果使用加法，请使用 += 而不是 = +，因为后者复杂度是 \(O(|A|+|B|)\) 的。
模板
（当前字符串为中心的最长回文串长度为 \(p_i-1\)）
int p[N],l,r;
void manacher(string t){
string s="#";
repl(i,0,t.size())s+=t[i],s+='#';
p[0]=1;l=r=0;int len=s.size();
repl(i,1,len){
if(i<=r&&p[l-(i-l)]<r-i+1)p[i]=p[l-(i-l)];
else p[i]=max(1,r-i+1);
while(i+p[i]<len&&i-p[i]>=0&&s[i+p[i]]==s[i-p[i]])p[i]++;
if(i+p[i]-1>r)r=i+p[i]-1,l=i;
}
}
例题
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define repl(i,x,y) for(int i=(x);i<(y);i++)
#define per(i,x,y) for(int i=(x);i>=(y);i--)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
const int N=2.2e7+5;
string s;
int ans=1;
int p[N],l,r;
void manacher(string t){
string s="#";
repl(i,0,t.size())s+=t[i],s+='#';
p[0]=1;l=r=0;int len=s.size();
repl(i,1,len){
if(i<=r&&p[l-(i-l)]<r-i+1)p[i]=p[l-(i-l)];
else p[i]=max(1,r-i+1);
while(i+p[i]<len&&i-p[i]>=0&&s[i+p[i]]==s[i-p[i]])p[i]++;
if(i+p[i]-1>r)r=i+p[i]-1,l=i;
chmax(ans,p[i]-1);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>s;
manacher(s);
cout<<ans;
return 0;
}