「十二省联考2019」字符串问题

重工业,,,

题意简述

给定一个字符串 S,再给定 nA 个 A 类串和 nB 个 B 类串(均为 S 的字串)。定义 A 类串的权值为该串长,B 类串的权值为 0。

将这些字串抽象为点,给定 m 条 A 类连向 B 类的边。定义一个 B 类串向某个 A 类串连边当且仅当其为该 A 类串的一个前缀。

求一条最长的路径(路径长度定义为路径上经过所有点的权值和),需判断无解。|S|,nA,nB,m2×105

[LOJ 3049]

[Luogu 5284]

主要思路

由于不会 SAM,此处只讲 SA 做法。

假设 xy 的前缀,那么 x 的字典序必定小于 y,且 lcp(x,y)=|x|

于是只需要把 A 串和 B 串一起按字典序排好序,然后对每个 B 串二分一下它为前缀的区间,线段树优化建图,拓扑排序,就喜提 O(nlogn)

怎么按字典序排序?对于俩串,lcp 为较短的,则短的排在长的前面;lcp 比最短的还短,直接按SA::rk[]排即可。

参考代码

注意细节,比如 B 串应该在有相同 A 串时居于前面。

不知道为啥常数巨大,可能我写丑了?

0 comments
Anonymous
Markdown is supported

Be the first guy leaving a comment!