社区讨论

求帮忙查错,洛谷AC,bzojWA了

P3649[APIO2014] 回文串参与者 1已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi7dz7vc
此快照首次捕获于
2025/11/20 20:07
4 个月前
此快照最后确认于
2025/11/20 20:07
4 个月前
查看原帖
这题bzoj的数据比较强。。。
CPP
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 300000 + 5;

struct PAM
{
	int nxt[maxn][26], link[maxn], len[maxn], size[maxn], sz, last;
	int s[maxn];
	
	void inline extend(int c, int now)
	{
		int p = last;
		while(s[now - len[p] - 1] != s[now]) p = link[p];
		if(!nxt[p][c]) {
			int q = link[p];
			while(s[now - len[q] - 1] != s[now]) q = link[q];
			link[++sz] = nxt[q][c], nxt[p][c] = sz, len[sz] = len[p] + 2;
		}
		last = nxt[p][c]; ++size[last];
	}
	
	void inline build(char *str)
	{
		for(int i = 0; str[i]; ++i) s[i + 1] = str[i] - 'a';
		link[0] = link[1] = 1; len[0] = 0, len[1] = -1;
		sz = 1;
		for(int i = 0; str[i]; ++i) extend(s[i + 1], i + 1);
//		for(int i = sz; i > 1; --i) size[link[i]] += size[i];
	}
} pam;

char str[maxn];

void inline Solve()
{
	ll ans = 0;
	pam.build(str);
	for(int i = pam.sz; i > 1; --i) ans = max(ans, (ll)pam.size[i] * pam.len[i]), pam.size[pam.link[i]] += pam.size[i];
	printf("%lld\n", ans);
}

int main()
{
	scanf("%s", str);
	Solve();
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...