Boring counting
\[ Time Limit: 1000 ms \quad Memory Limit: 32768 kB \]
题意
给出一个字符串，求出其中出现两次及以上的子串个数，要求子串之间不可以重合。
思路
在 \(SAM\) 上对于节点 \(i\) ，其包含的子串长度范围为 \(\left[maxlen\left(father\right)+1，maxlen\left(i\right) \right]\)，在考虑节点\(i\)的 \(endpos\)，设出现的最左位置为 \(left\)，最右位置为 \(right\)，如果我们可以得到 \(left\) 和 \(right\)，我们就可以进行如下的讨论：
- 首先明确 \(right-left\) 是同一子串两次出现位置最大距离，我们考虑在这个距离中，可以不重合的放下多少子串。
若 \(right-left \geq maxlen(i)\)，距离足够大放下节点 \(i\) 可以表示的最长子串。这说明对于节点 \(i\) 包含的所有子串，都能满足不重合的出现两次。一共有 \(maxlen(i)-maxlen(father)\) 种子串符合条件。
若 \(right-left \leq maxlen(father)\)，此时距离太小，无法放下节点 \(i\) 可以表示的最短子串。这说明对于节点 \(i\) 包含的所有子串，都无法满足不重合的出现两次。
若 \(maxlen(father) < right-left < maxlen(i)\)， 此时距离只够放下其中的一部分子串。这时候容易得到，可以放下的子串的长度范围为 \(\left[maxlen(father)+1，right-left\right]\)，也就是有 \(right-left-maxlen(father)\) 种子串符合条件。
综合上面三种情况，整理起来就是
- 若 \(right-left \leq maxlen(father)\)，对答案贡献0。
- 否则，对答案贡献 \(min(right-left，maxlen(i)) - maxlen(father)\)。
那么如何得到 \(left\)和\(right\)？
- 对于 \(left\)，每个子串第一次出现的位置，一定就是他的 \(left\)。
- 对于 \(right\)，因为 \(endpos(i) \in endpos(father)\)，所以将每个节点的 \(left\) 往其 \(father\) 上更新最大值，就是 \(father\) 的 \(right\)，如此倒着求 \(right\)。
/*************************************************************** > File Name : a.cpp > Author : Jiaaaaaaaqi > Created Time : 2019年05月23日 星期四 00时06分46秒 ***************************************************************/#include