Annihilate
题目背景
前情提要：小正方形与黑暗之主展开了大战，最后小正方形击败了黑暗之主，成功从黑暗之主的手上夺下最后一个三角。
三角旋转着，净化着，正当三角即将净化完成时，黑暗之主突然到来，阻断了三角形的净化，吸收了三角的能量。
可是，因为三角的能量太过巨大，导致黑暗之主发生了变异，现在的黑暗之主一次次复制，最终成为了一条蜈蚣……
现在，小正方形还能阻止黑暗之主毁灭世界吗？
题目描述
黑暗之主的蜈蚣几乎可以毁灭一切，因此小正方形陷入了苦战……
小正方形现在需要减弱黑暗之主的攻击。
一个黑暗之主的攻击可以用一个仅有小写字母的字符串表示。
现在黑暗之主向小正方形发动了若干攻击，对于两个攻击，小正方形能选出它们最长的公共子串，并把这一段消除。
现在小正方形想要知道，对于任意两个黑暗之主的攻击，它们的最长公共子串长度是多少，你能帮帮它吗？
输入输出格式
输入格式：
第一行为一个整数 nn，表示字符串数目。
接下来 nn 行，一行一个字符串，保证所有字符串长度之和 <= 1000000
输出格式：
输出共有 nn 行，每行 n - 1n−1个正整数
第一行第一个正整数表示第1个串与第2个串的最长公共子串
第二个正整数表示第1个串与第3个串的最长公共子串
……
第二行第一个正整数表示第2个串与第1个串的最长公共子串
以此类推。
输入输出样例
输入样例#1：
1 | 3 |
输出样例#1：
1 | 1 2 |
说明
对于 30\%30% 的数据，n <= 5n<=5，每个字符串长度 <= 500<=500
对于 100\%100% 的数据，2 <= n <= 502<=n<=50，字符串长度之和 <= 1000000<=1000000
注意：本题内存限制仅为 64 MB,请尽量使用内存运用优秀的方法。
另外，对于占 60 Pts 的测试点，您每通过一个点即可获得 10 Pts
对于剩下的测试点，您只有全部通过才能获得 40 Pts.
对于所有数据点，不保证数据为随机生成。
Solution
挺简单（没写代码
把它们收尾相接连在一起计算出后缀数组。
然后开始按照排名枚举后缀（也就是$sa$数组，按照位置枚举就是$rank$数组）
对每个串$k$只需要记录一下前驱后缀$pre_k$（就是之前最后一次出现的后缀）
因为是按照排名枚举，所以肯定对于当前后缀所属的串$T$ , 与其他串$k$最大的答案肯定是从每次的$pre_k$两个后缀之间的$LCP$产生的（因为排名差的越小$LCP$可能越大，换句话说，$LCP$长度随着排名差的增大单调不增，这是平凡性质）
然后我们只需要一种$O(1)$的RMQ即可。
但是不知道出题人什么心理64MB空间。。
但是$n$非常的小emmmm.
然后我们考虑把后缀按照所属串分个类，然后依然按照排名枚举，用个数组维护每个串上一个后缀出现位置后面的$h$数组的最小值，然后每个后缀$sa_i$被枚举后，只需要$O(n)$的暴力维护这个后缀所属串的后缀最小值。
但事实上我们只需要把内存开大一点即可。
Code：does not exist