题面 P3975 [TJOI2015]弦论 Solution 看到题面要求不同情况下的$K$小串，给人一种自动机上做DP就可以写的感觉。 因此，我们考虑用后缀自动机来解决这个问题。我们先建出SAM。 对于$k=0$的情况，肥肠好写。根据SAM的常识，在SAM上任意走都是原串的一个子串。题目要求求出第$k$小不重复子串，既是让我们求出SAM的前$k$条路径。因为这里的$k$很大，我们是不能暴力...

题面 传送门：SPOJ 694 Solution 这题可以用SAM来搞，也可以用SA来搞。但无论是哪种搞法，都是基本操作。下面我们来分别讲解一下怎么搞。 SAM 这题用SAM来求就十分粗暴简单。不会SAM的小伙伴可以戳这里 首先，我们先把SAM建出来。根据SAM的性质，我们从出发点随着SAM任意走，走到哪里都是一个完全不同的子串。因此，我们只需要对SAM做一个拓扑序DP/记忆化搜索即可求出...