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