题面 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/记忆化搜索即可求出...

题面 洛谷 P2743 Solution 这题可以用哈希做，也可以用SA做。下面我们分别讲一下两种做法。 哈希 首先，我们把转掉的问题处理掉。我们考虑把原串做差分数组，即用后面那一个减去前面那一个。这样子，我们直接在新的串上找完全相同的两个不可重叠子串即可。 这个，我们考虑先在外面二分一个答案的长度，然后暴力做，从后往前扫，把所有子串都丢到哈希表里面，插入一个新的串之前，就检查一下之前是否...

题面 传送门：洛谷P2852 Solution 首先，我们阅读题面可以发现题目让我们求出一个出现次数>k的可重复的子串。 这玩意我们可以用SA求，也可以用SAM求。 SA 这题用SA做就比较妙，首先我们显然要求把SA及height求出来。 因为两个后缀的LCP是它们之间的height的min，我们可以利用这个性质。 考虑一个子串，它所能“控制”的区间的所有的height都必须比它大。...

为什么要学后缀数组 为了解决一类字符串神题妙题。 什么是后缀数组 什么是后缀 要理解什么是后缀数组，首先要明白什么是后缀。 一个字符串$[S_1:S_n]$的后缀为:$[S_i:S_n],i∈[1,n]$ 用人话来说，就是从每个字符开始到这个字符串的结尾所组成的串均为这个字符串的后缀。 例如： 假设我现在有一个字符串“abaaba”,那么。她的后缀有：a,ba,aba,aaba,baaba...