P3649 [APIO2014]回文串
传送门
题目描述
给你一个由小写拉丁字母组成的字符串 $s$。我们定义 $s$ 的一个子串的存在值为这个子串在 $s$ 中出现的次数乘以这个子串的长度。
对于给你的这个字符串 $s$，求所有回文子串中的最大存在值。
输入输出格式
输入格式：
一行，一个由小写拉丁字母（a~z）组成的非空字符串 $s$。
输出格式：
输出一个整数，表示所有回文子串中的最大存在值。
输入输出样例
输入样例#1：
abacaba
输出样例#1：
7
输入样例#2：
www
输出样例#2：
4
说明
【样例解释1】
用 $\lvert s \rvert$ 表示字符串 s 的长度。
一个字符串 $s_1 s_2 \dots s_{\lvert s \rvert}$的子串是一个非空字符串 $s_i s_{i+1} \dots s_j$，其中 $1 \leq i \leq j \leq \lvert s \rvert$。每个字符串都是自己的子串。
一个字符串被称作回文串当且仅当这个字符串从左往右读和从右往左读都是相同的。
这个样例中，有 $7$ 个回文子串 a，b，c，aba，aca，bacab，abacaba。他们的存在值分别为 $4, 2, 1, 6, 3, 5, 7$。
所以回文子串中最大的存在值为 $7$。
第一个子任务共 8 分，满足 $1 \leq \lvert s \rvert \leq 100$。
第二个子任务共 15 分，满足 $1 \leq \lvert s \rvert \leq 1000$。
第三个子任务共 24 分，满足 $1 \leq \lvert s \rvert \leq 10000$。
第四个子任务共 26 分，满足 $1 \leq \lvert s \rvert \leq 100000$。
第五个子任务共 27 分，满足 $1 \leq \lvert s \rvert \leq 300000$。
分析
看到“定义 $s$ 的一个子串的存在值为这个子串在 $s$ 中出现的次数乘以这个子串的长度“,第一反应这不是P3804的定义吗。
于是…嗯…$SAM$！！！其实是因为我是搜$SAM$的标签搜到的这题
嗯…打一发…
哦~过了样例。
开心ing…
交一发….
等等！开不开long long。
算一波极限,赋值一下,编译器告诉我—-overflow in implicit constant conversion。
哦~看来要开long long。
交一发….
额~50分？？？
为什么只有50分？？？我的$SAM$打错了？？？
懵逼ing…
哦~回文串嘛。为什么直接求所有子串的存在值有50分？？？
可是回文串怎么做？？？
题解….
$SAM$套$Manacher$加倍增？？？好麻烦不打，复杂度还是$O(nlogn)$的，还被卡空间….
嗯~纯$SAM$的，可是…图呢？？？没图我怎么知道你在说什么？？？
网上一搜…又搜到一篇…还是没图(确切的说，是当时没图)…
放弃…
颓废ing…
算了，回文自动机正等着我…
学习ing…
发现我的回文自动机没初始化特殊字符？？？(即$s_0=-1$)，还是过了？？？
算了，不再交了，放代码的时候加上算了。
参考资料
纯$SAM$
回文自动机
大奕哥&VANE的 Palindromic Tree 回文自动机-回文树 例题+讲解 主要学习资料
Clove_unique的 Manacher 回文自动机 学习笔记 主要是为了看图
冯钰恒的 回文树/回文自动机/PAM总结——题解 P3649 【[APIO2014]回文串】 主要参考代码实现
F.W.Nietzsche的 回文树或者回文自动机，及相关例题
KSKUN的 回文自动机原理与实现
Update
asuldb的题解刷新一波又有图了，于是再学…为什么我做的时候你没图，做完就有图了！！！
代码
第一份傻逼的错误代码
写了这么久好歹还是放一下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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
using namespace std;
template <typename T>inline T read()
{
register T sum=0;
register char cc=getchar();
int sym=1;
while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
if(cc=='-')sym=-1,cc=getchar();
sum=sum*10+cc-'0';
cc=getchar();
while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
return sym*sum;
}
template <typename T>inline T read(T &a)
{
a=read<T>();
return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
a=read(a);
read(b...);
}
int n,las=1,cnt=1,ton[maxn<<1],ns[maxn<<1],len[maxn<<1],siz[maxn<<1],fa[maxn<<1],ch[maxn<<1][26];
long long ans;
char str[maxn];
void add(int c)
{
int p=las,np=las=++cnt;
siz[np]=1;
len[np]=len[p]+1;
for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
if(!p)fa[np]=1;
else
{
int q=ch[p][c];
if(len[q]==len[p]+1)fa[np]=q;
else
{
int nq=++cnt;
fa[nq]=fa[q];
len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[q]=fa[np]=nq;
for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;
}
}
}
int main()
{
scanf("%s",str);n=strlen(str);
for(int i=0;i<n;i++)add(str[i]-'a');
for(int i=1;i<=cnt;i++)ton[len[i]]+=1;
for(int i=1;i<=cnt;i++)ton[i]+=ton[i-1];
for(int i=1;i<=cnt;i++)ns[ton[len[i]]--]=i;
for(int i=cnt;i>=1;i--)
{
siz[fa[ns[i]]]+=siz[ns[i]];
ans=max(ans,1ll*len[ns[i]]*siz[ns[i]]);
}
printf("%lld\n",ans);
return 0;
}
回文自动机
1 |
|