程序地带

[SNOI2020]字符串


题目

传送门 to luogu


思路

题目转化:将子串们两两匹配,使得

l
c
p
sum m lcp
∑lcp 最大。


不难发现,对于
A
A
A 的以
x
x
x 开头的子串,肯定要多多和
B
B
B 中以
x
x
x 开头的子串配对才好!


证明很简单。假如
A
A
A 中某个匹配的不是
B
B
B 中以
x
x
x 开头的,
B
B
B 中也有一个,那么这两对的贡献都是
0
0
0 。交换匹配,至少会有
1
1
1 的贡献。


有了这个,可以直接用后缀数组排序,然后对于每种字符作为开头的子串,递归地处理。多出来的肯定就直接和不同字符开头的内部消化一下呀。


不难发现,如果每一步都有分叉,那么最多
O
(
n
)
mathcal O(n)
O(n) 步就会递归到头。求儿子对应管辖区间如果用二分查找,复杂度就是
O
(
n
log

n
)
mathcal O(nlog n)
O(nlogn) 的。问题在于,不分叉怎么办?不分叉,就说明当前区间内有一个
l
c
p
m lcp
lcp ,所以利用
h
e
i
g
h
t
height
height 直接跳过
l
c
p
m lcp
lcp 就必然有分叉了。


复杂度
O
(
n
log

n
)
mathcal O(nlog n)
O(nlogn) 。


他山之石:将串翻转,用
S
A
M
t SAM
SAM ,后缀树上的
l
c
a
lca
lca 就是
l
c
p
m lcp
lcp 了,然后类似一个树形
d
p
t dp
dp 。(其实就是上面的那个贪心啊,子树内尽力匹配。)


代码

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_42101694/article/details/112689105

随机推荐

SSH远程访问及控制

SSH远程访问及控制一、SSH远程管理(一)、定义SSH(SecureShell)是一种安全通道协议,主要用来实现字符界面的远程登...

[email protected] 阅读(958)

Flutter(dart) 理论知识.日积月累

理论知识.日积月累1.const和final的区别2extends,with和implements的区别我筑起高墙,只为了跟你锁在一起,不离不弃。——皇子1.const和f...

正在蜕变的CV工程师 阅读(493)

JUSTCTF2020 新生赛(校内)wp

JUSTCTF2020Crypto&MiscwpCrypto1.CryptoSignIN打开附件可以得到如下的颜文字゚ω゚ノ=/`&#x...

浮岚丶暖阳 阅读(619)

w5500网络连接状态判断

通过判断PHY寄存器的LINK位对连接状态进行判断,为1表示有连接,0表示无连接。#definePHYCFGR(0x002E00)#defineRST_PHY0x80#de...

梦里啥都有、 阅读(681)

HRP标记山羊抗兔/抗属IgG相关研究

HRP标记山羊抗兔/抗属IgG相关研究

JacksonImmmoResecarch特色科研产品在细胞生物学,蛋白质化学,微生物学,免疫学及产品开发实验方面,有着比较深入的研究ÿ...

艾美捷 Amy 阅读(745)