【JZOJ7839】神秘代码
凯尔希我谢谢你
lcp的题所以考虑使用 $ S A $ 或者 $ SAM $
此处使用大佬提供的 $ SA $ 思路
Part I
首先我们考虑不反转怎么做
这其实是一道SA板子题
我们将所有的字符串全部用特殊符号隔开变成一个大字符串
然后把每个点的 $ height $ 数组跑出来
对于每一个点的 $ height $ 值我们独立算贡献
怎么算？
前置芝士1 ： 将 $ height $ 按照 $ SA $ 跑出来的排名排序，对于任意两个后缀 $ i $ 和 $ j $，它们的 $ LCP $ 即为
\[ \min_{k=i+1}^j hi_k
\]
所以我们就可以对于每一个 $ hi_i $ ,运用二分加 $ ST $ 表的思想，找出最左&最右边的 $ hi_j \ge $ 自己的位置
统计数量再乘上 $ hi_i $即可~
Part II
接下来我们考虑加上反转这个限制
死亡不是终点，被遗忘才是。——寻梦环游记