title : 斯坦纳树tags : ACM 图论date : 2021-6-26author : Linno什么是斯坦纳树给定 nn 个点 A1,A2,⋯,AnA1,A2,⋯,An，试求连接此 nn 个点，总长最短的直线段连接系统，并且任意两点都可由系统中的直线段组成的折线连接起来。他们将此新问题称为 斯坦纳树问题。斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给

title : 后缀自动机date : 2021-11-11tags : ACM,字符串author : Linno前置知识KMP，Trie，AC自动机等字符串基础DFA（有限状态自动机）后缀自动机(Suffix automaton ,SAM)定义字符串s的SAM是一个接受s的所有后缀的最小DFA（确定性有限自动机）。直观上SAM是给定字符串的所有字串的压缩形式。而构造的时间复杂度和空间复杂度仅为