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;	
}

模板二