[NOI2012] 美食节
作为一个喜欢尝鲜的美食客,小 M 自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而,尝鲜的欲望是难以满足的。尽管所有的菜品都很可口,厨师做菜的速度也很快,小 M 仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小 M 开始研究起了做菜顺序的问题,即安排一个做菜的顺序使得同学们的等待时间最短。
题目传送门思路对于一个字符串 $s$,$z_i := |\operatorname{LCP}(s,s[i:])|$,即 $s$ 从 $i$ 开始的后缀与 $s$ 的最大匹配。暴力计算 $z$ 函数是 $O(n^2)$ 的,考虑将计算的 $z$ 函数用起来。我们顺次计算 $z$ 函数,假设现在需要计