重工业,,,
题意简述
给定一个字符串 $S$,再给定 $n_A$ 个 A 类串和 $n_B$ 个 B 类串(均为 $S$ 的字串)。定义 A 类串的权值为该串长,B 类串的权值为 0。
将这些字串抽象为点,给定 $m$ 条 A 类连向 B 类的边。定义一个 B 类串向某个 A 类串连边当且仅当其为该 A 类串的一个前缀。
求一条最长的路径(路径长度定义为路径上经过所有点的权值和),需判断无解。$|S|, n_A, n_B, m\le 2\times 10^5$。
主要思路
由于不会 SAM,此处只讲 SA 做法。
假设 $x$ 为 $y$ 的前缀,那么 $x$ 的字典序必定小于 $y$,且 $\operatorname{lcp}(x, y) = |x|$。
于是只需要把 A 串和 B 串一起按字典序排好序,然后对每个 B 串二分一下它为前缀的区间,线段树优化建图,拓扑排序,就喜提 $O(n\log n)$。
怎么按字典序排序?对于俩串,lcp 为较短的,则短的排在长的前面;lcp 比最短的还短,直接按SA::rk[]
排即可。
参考代码
注意细节,比如 B 串应该在有相同 A 串时居于前面。
不知道为啥常数巨大,可能我写丑了?
1 |
|