[luoguP2336] [SCOI2012]喵星球上的点名（后缀数组 + 暴力）传送门原本的想法是把所有的串不管是名字还是询问都连起来，记录一下询问串在sa数组中的位置对于每个询问可以在sa数组中二分出左右边界，第一问用莫队，第二问差分乱搞。结果发现
[luoguP2463] [SDOI2008]Sandy的卡片（后缀数组 + st表）传送门很容易想到，题目中的相同是指差分数组相同。那么可以把差分数组连起来，中间加上一个没有出现过的且字典序小的数双指针移动，用st表维护height数组中的最小值。当然用单调
[POJ1226]Substrings（后缀数组）传送门
给定 n 个字符串，求出现或反转后出现在每个字符串中的最长子串。
算法分析:
这题不同的地方在于要判断是否在反转后的字符串中出现。其实这并没有加大题目的难度。
后缀数组模板题
蒙蔽，先背着，说不定哪天就开窍了。
半年后，真的自己开不了窍，还是得有人讲才能明白些。
于是我先记录一下我对于后缀数组的理解吧。
算了还是写在代码注释中吧。。。
[POJ3294]Life Forms（后缀数组）传送门
统计大于一半的串中都出现过的子串，有多个按照字典序输出
二分子串长度 k，用 k 将height 数组分组，接下来直接判断就 ok。
有个小细节，平常统计所有串中都出现的最长
[POJ3974]Palindrome（后缀数组 || manacher）传送门
求一个串的最长回文子串的长度
1.后缀数组
把这个串反转后接到原串的后面，中间连一个没有出现过的字符。
然后求这个新字符串的某两个后缀的公共前缀的最大值即可
[TyvjP1515] 子串统计 [luoguP2408] 不同子串个数（后缀数组）Tyvj传送门
luogu传送门
经典题
统计一个字符串中不同子串的个数
一个字符串中的所有子串就是所有后缀的前缀
先求出后缀数组，求出后缀数组中相邻两后缀的 lcp
那么按照后
[POJ2406]Power Strings传送门
给定一个字符串 L，已知这个字符串是由某个字符串 S 重复 R 次而得到的，求 R 的最大值。
1.后缀数组
做法比较简单，穷举字符串 S 的长度 k，然后判断是否满足。判断的时
[HDU2328]Corporate Identity（后缀数组）传送门
求 n 个串的字典序最小的最长公共子串。
和 2 个串的处理方法差不多。
把 n 个串拼接在一起，中间连上一个没有出现过的字符防止匹配过界。
求出 height 数组后二分
[luoguP2870] [USACO07DEC]最佳牛线，黄金Best Cow Line, Gold（后缀数组）传送门
数据小的话贪心就行。
可以把这个串翻转再接到后面，再求后缀数组，求出 rank 数组就很简单了。
——代码
1 #include <cstdio>
2 #include <iostream>
3 #defi
[HDU3518]Boring counting（后缀数组）传送门
求出现超过1次的不重叠子串的个数
根据论文中的方法。
枚举子串的长度 k。
用 k 给 height 数组分组，每一组求解，看看当前组的位置最靠后的后缀和位置最靠前的后缀
[HDU1403]Longest Common Substring（后缀数组）传送门
求两个串的公共子串（注意，这个公共子串是连续的一段）
把两个串连在一起，中间再加上一个原字符串中不存在的字符，避免过度匹配。
求一遍height，再从height中找满足条件的
[BZOJ1031][JSOI2007]字符加密Cipher（后缀数组）传送门
算是个模板。
题目说循环，那就再复制一串拼接上。
然后求后缀数组，再搞就可以。
虽然是求后缀，会在后面多一些字符串，然而题目中说的是循环一圈，但是没有影响。
——
