Manacher
Manacher的几个模板
模板一
前后插入不等的特殊字符 ( 不用写越界的判断条件 )
中间用 # 隔离 ( 不用判断奇偶 )
#include <bits/stdc++.h>
using namespace std;
const int N = 22000005;
char s[N],t[N];
int cnt , mr , mid , len[N];
void build()
{
cin >> s;
t[++cnt] = '~' , t[++cnt] = '#';
int n = strlen(s);
for(int i = 0 ; i < n ; ++i)
t[++cnt] = s[i] , t[++cnt] = '#';
t[++cnt] = '!';
}
void Slove()
{
int ans = 0;
for(int i = 2 ; i <= cnt - 1 ; ++i){
if(i <= mr) len[i] = min(len[2 * mid - i] , mr - i + 1);
else len[i] = 1;
while(t[i - len[i]] == t[i + len[i]]) ++len[i];
--len[i];
if(i + len[i] > mr) mid = i , mr = i + len[i];
ans = max(ans , (len[i] * 2 + 1 ) / 2 );
}
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
return build() , Slove() , 0;
}
模板二