manacher模板求解释
  • 板块学术版
  • 楼主sundyLIUXY
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/1/30 12:10
  • 上次更新2023/10/24 02:35:05
查看原帖
manacher模板求解释
706737
sundyLIUXY楼主2023/1/30 12:10

上网查了不是很懂,求详细解释

#include<bits/stdc++.h>
using namespace std;

char s[11000010],st[21000010];
int p[21000010], len, ans;

void init()
{
	st[0] = '!', st[1] = '#';
	for(int i = 0; i < len; i++)
		st[2*i+2] = s[i], st[2*i+3] = '#';
	len = len*2+2, st[len] = '@';
}
void manacher()
{
	int id = 0, ma = 0;
	for(int i = 1; i < len; i++)
	{
		p[i] = ma > i ? min(p[2*id-i], ma-i) : 1;
		for(; st[i+p[i]] == st[i-p[i]]; p[i]++)
			if(p[i]+i > ma) ma = p[i]+i, id = i;
		ans = max(ans, p[i]-1);
	}
}

int main()
{
	scanf("%s", s);
	len = strlen(s);
	init(), manacher();
	printf("%d", ans);
	
	return 0;
}

ma是啥?p[]里面是啥?id是啥?

2023/1/30 12:10
加载中...