P4081 [USACO17DEC] Standing Out from the Herd P
只有一个串怎么做？
那就是 P2408 不同子串个数。
跑一遍后缀排序，按排序结果遍历后缀，考虑每个后缀会产生多少新串。
为保证每个不同的串只被记录一次，只考虑去掉它与上一个串的重复部分，即为 \(height_i\)。
多个串类似，在串中加上分隔符跑 SA，给每个位置记录一下它原来属于哪个串。
同一个串之间的去重与上面同理，只不过求 lcp 要写个 ST 表什么的求最小值（可能不用？）。现考虑不同串之间的去重。
由于一个后缀与其它后缀的 lcp 越往前越小，越往后越小（因为取 \(\min\)），因此只用向前向后都找到第一个不属于同一个串的后缀并取 lcp。
把上面 3 个lcp 长度取 \(\max\) 就是应该去掉的串数。
P2603 [ZJOI2008] 无序运动
一组点就是一堆首尾相接的向量形成的链。
不考虑沿 \(x\) 轴翻转的情况，相邻向量之间的 长度之比 和旋转的 有向角度 不变。因此以这个东西为特征值表示一组点。于是就是一个字符集巨大的 \(\text{ACAM}\)。
听说在 \(ch[u][i]\) 不存在时 暴力跳 fail 是对的，看看这个，我不会证。
翻转时 有向角度 会变成负的，解决方法是把给的点集沿 \(x\) 轴翻转后再匹配一次，加起来。
五百万车细节，挂了 16 发。
标签：lcp,后缀,练习,越小,字符串,考虑,向量,翻转 From： https://www.cnblogs.com/jimmywang/p/17570846.html