UOJ Logo matthew99的博客

博客

UOJ494:DNA序列 做法简要描述

2019-12-30 17:47:17 By matthew99

题面

http://uoj.ac/problem/494

做法简要描述

首先,每个字符串后面加一个很大的字符(例如“U”)。

对于每个字符串$s$,找到最短的前缀$x$满足$x ^ \infty < s$,然后将字符串$s$分成$x ^ y + z$, 使得$x$不是$z$的前缀。

那么合并的顺序一定是按照$x^\infty$字典序升序然后相同按照$z+U$字典序降序,注意使用字母U的原因是U比四个字母都要大。

感性的理解就是这样,每次我们希望找个最小的$x$,然后加入尽量多的$x$,但是$x$加完之后我们希望能加的字符尽量小,所以我们把尾巴字典序最小的放后面。

知道顺序之后,倒着枚举前缀的长度贪心就行了。

比如对于输入:

CCACCACCACCATA
CCACCACCACCACCACCCA
CCACCACCACCCAAA
G

那么前三个每个的$x$都是“CCA”,$z$分别是“TA”,“CCCA”和“CCCAAA”,我们把第三个放后面,那么就有

“CCACCACCACCACCACCACCACCACCACCACCACCACCCAAA”

最后再加入“G”。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。