• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

字符串杂题

开发技术 开发技术 4天前 7次浏览

Little Elephant and Strings

来源:CF204E

做法一:( $mathrm{SA}+$ 主席树)   

可以把所有串拼在一起,然后中间用特殊分隔符分开.   

考虑处理第 $mathrm{i}$ 个串的 $mathrm{l}$ 位置开始的子串. 

显然这个 $mathrm{r}$ 具有单调性,所以可以二分最大的 $mathrm{r}$. 

然后在区间里用主席树查询一下不同串的编号种类即可.   

时间复杂度为 $mathrm{O(n log^2 n)}$.   

 


程序员灯塔
转载请注明原文链接:字符串杂题
喜欢 (0)