Manacher算法

首先，请出大佬的文章：
https://blog.csdn.net/happyrocking/article/details/82622881
下面，开始蒟蒻的被虐史：（如果看不下去，跳转到大佬的文章！）

Manacher算法 模板

题目

描述 Description
题目： 最长回文串
求出一串字符串的最长回文串并输出。
输入格式 Input Format
输入仅为一行，为该字符串
输出格式 Output Format
输出仅一行，为该字符串最长的回文串，如果有相同长度的，输出最左边的即可。
样例输入 Sample Input
ThesampletextthatcouldbereadedthesameinbothordersArozaupalanalapuazorA
样例输出 Sample Output
ArozaupalanalapuazorA
时间限制 Time Limitation
3s
注释 Hint
字符串长度：1<=len<=100000
来源 Source
模板题
by Mybing

模板

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+1e3;
char s1[maxn];//原字符串 
char s2[maxn];//经过处理的字符串 
int p[maxn];//半径数组 
int main()
{
	cin>>s1;
	int n=strlen(s1),len=0;
//	字符之间插入特殊字符
	s2[len++]='$';
	for (int i=0;i<n;++i)//切记：从零开始
	{
		s2[len++]='#';
		s2[len++]=s1[i];
	}
	s2[len++]='#';
//	计算半径数组p
	int mx=0;//回文子串的最后位置
	int id=0;//回文子串的中心位置
	int maxn=0,loc=0;//最长回文子串的半径大小以及开始地址 
	for (int i=1;i<len;++i)
	{
		if (i<mx)//如果mx在i的右边
			p[i]=min(mx-i,p[2*id-i]);
		else  p[i]=1;
//		尝试继续向两边扩展，更新p[i]
		while (s2[i+p[i]] == s2[i-p[i]])//不必判断是否溢出，因为首位均有特殊字符，肯定会退出
			++p[i];
//		更新中心
		if (i+p[i]>mx)
			mx=i+p[i],id=i;
//		更新最长串
		if (p[i]>maxn)
			maxn=p[i],loc=i;
	}
	for (int i=loc-p[loc]+2;i<=loc+p[loc]-2;i+=2)
		printf("%c",s2[i]);
	printf("\n");
	return 0; 
}

例题

<马拉车>三元组

题目

描述 Description
给定一个字符串S，求满足1≤i≤j＜k≤|S|且S[i…j]与S[j+1…k]都是回文子串的所有三元组(i,j,k)的∑i·k之和。由于答案可能较大，你只需要给出结果模1000000007后的值即可。
输入格式 Input Format
第一行一个整数T表示数据组数。
每组数据仅一行一个字符串S。保证S中只包含小写英文字母。
输出格式 Output Format
对于每组数据输出一行一个整数表示答案。
样例输入 Sample Input
2
aaa
abc
样例输出 Sample Output
14
8
时间限制 Time Limitation
2s
注释 Hint
30%的数据：|S|≤100
60%的数据：|S|≤10000
100%的数据：|S|≤1000000，1≤T≤5
来源 Source
省选模拟题
by Mybing

代码

<马拉车>最长双回文串

题目

https://www.luogu.org/problemnew/show/P4555

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+1e3;
char s1[maxn],s2[maxn];
int p[maxn],ll[maxn],rr[maxn],ans=0;
int main()
{
	cin>>s1;
	int n=strlen(s1),len=0;
	s2[len++]='$';
	for (int i=0;i<n;++i)//切记：从零开始
	{
		s2[len++]='#';
		s2[len++]=s1[i];
	}
	s2[len++]='#';
	int mx=0,id=0;
	for (int i=1;i<len;++i)
	{
		if (i<mx)
			p[i]=min(mx-i,p[2*id-i]);
		else	p[i]=1;
		while (s2[i+p[i]] == s2[i-p[i]])
			++p[i];
		if (i+p[i]>mx)
			mx=i+p[i],id=i;
		ll[i+p[i]-1]=max(ll[i+p[i]-1],p[i]-1);
        rr[i-p[i]+1]=max(rr[i-p[i]+1],p[i]-1);
    }
    for (int i=1;i<len;i+=2)
		rr[i]=max(rr[i],rr[i-2]-2);
    for (int i=len-1;i>=1;i-=2)
		ll[i]=max(ll[i],ll[i+2]-2);
    for (int i=1;i<len;i+=2)
		if (rr[i]&&ll[i])
			ans=max(ans,ll[i]+rr[i]);
    printf("%d\n",ans);
    return 0;
}