为了方便把串反过来，条件变为(t_i)是(t_{i+1})的真子串，答案显然不变。
一件重要的事情是必定存在一种最优解，字符串序列({t})满足(|t_i| = i)。
考虑DP：设(f_i)表示字符串序列({t})的最后一个串的结尾位置为(i)时，(|t|)的最大值。不难发现如果(f_i = x)，那么一定存在最后一个串结尾位置为(i)、长度在([1,x])内的字符串序列。
因为有(f_i leq f_{i-1}+1)（因为对于一个能够满足序列长度为(f_i)、最后一个串结尾为(i)的字符串序列(t)，把第一个字符串删掉，然后把其他的串的最后一个字符删掉，就可以得到序列长度为(f_i - 1)、最后一个串结尾为(i-1)的一个合法的字符串序列），所以可以从大到小枚举(f_i)的合法取值，这里的总check次数是(O(n))的。
那么问题变成如何check。考虑我们实际上只需要满足(s_{1,i - f_i})中是否存在一个(s_{i - f_i + 1 , i})的子串满足该串的结尾的(f)值大于等于(f_i - 1)。注意到可能满足条件的只有两个子串（(s_{i - f_i + 1 , i - 1})和(s_{i - f_i + 2 , i})），所以我们只需要知道这些点所有(leq i - f_i)的endpos中的(f)值的最大值。注意到(i - f_i)是单调不降的，所以我们可以使用一个指针维护当前询问的前缀，在线段树上做单点修改、子树查询最大值即可。