string s;//原串
char str[N];//处理后的原串
int p[N]//存储以每个点为中心的最长回文子串的半径
int ans;//代表原串中最长的回文串的长度
int sum;//代表原串中回文串的个数（同类型算多次）
int init()//init操作可以让manacher同时求解奇数个数回文串和偶数个数回文串
{
    int len=s.length();
    str[0]='^';
    str[1]='$';
    int j=2;
    for (int i=0;i

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41

输出最长回文串模板

void printSub(int C, int R){//C代表中心，R代表半径
    for(int i = C - R+1  ; i < C+ R;){
        cout<=1)
            printSub(k, p[k]);
}
1
2
3
4
5
6
7
8
9
10
11
12

【模板】manacher 算法

题目描述

给出一个只由小写英文字符 $ \texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z $ 组成的字符串 $S$ ,求 $S$ 中最长回文串的长度 。

字符串长度为 $n$。

输入格式

一行小写英文字符 $\text{a},\text{b},\text{c},\cdots ,\text{y},\text{z}$ 组成的字符串 $S$。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

aaa
1

样例输出 #1

3
1

提示

$1\le n\le 1.1\times 10^7$。

AC代码

const int N = 3e7;//因为N的范围问题，re了好几次，能开大最好开到最大，因为str需要两倍的空间
char s[N];
char str[N];
int p[N];
int init()
{
	int len=strlen(s);
	str[0]='!';
	str[1]='#';
	int j=2;
	for(int i=0;ir)
		{
			mid=i;
			r=p[i]+i;
		}
		ans=max(ans,p[i]-1);
	}
	return ans;	
}
void solve()
{
	scanf("%s",s);
	cout<