GYM103145L.k-th Smallest Common Substring（后缀树）

2021/11/10 6:11:48

编程Tag： substring 后缀公共节点保留每个 common smallest 串里

本文主要是介绍GYM103145L.k-th Smallest Common Substring（后缀树），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

对每个串的反串建立广义后缀树

后缀树的dfs序就是字典序

对第一个串保留到位置[l]的节点编号

仅保留在所有串里都出现过的子串

对每个节点维护一颗线段树

后缀树上自底向上合并

在每个串里出现的节点，记为公共节点

然后对每个询问，二分找到对应的公共节点

然后对公共节点表示的字符串，直接根据当前k剩余的值获得长度

就做完了？

这篇关于GYM103145L.k-th Smallest Common Substring（后缀树）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！