文件名称：方法二－TimGreen大牛的方法-ACM资料 楼天城PPT
文件大小：510KB
文件格式：PPT
更新时间：2024-05-15 11:40:29
ACM
方法二－TimGreen大牛的方法 先坐出原数列差数列。对差数列建后缀树。 如果不要求不相交的话。因为每一个中间结点以下的子树至少有两个叶子。所以这个结点到根行成的单词一定是重复子串。那么只要对后缀树中和每一个中间结点看不看长度,找出最大的就是答案。 现在考虑相交的情况。 对于一个中间结点,它到根和单词可以是不相交和重复子串，它以下的叶子结点中有两个的长度差>=这个重复子串的长。 所以我们从下到上树形Dp,O(N)计算出每一个中间结点下的叶子结点长度的最大值和最小值。 O(N)