社区讨论
求帮忙查错,洛谷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 条回复,欢迎继续交流。
正在加载回复...