给定一个序列 a 和一个字符串 S。定义 w(T)=\sum\limits_{i\in endpos(T)}i。对于每个 i 求出 \sum\limits_{j=i}^n w(S[i,j])。
这个技巧和压缩后缀自动机以及对称压缩后缀自动机有一些奇妙的联系。
考虑同时建出后缀树和后缀自动机。
一个想法是在后缀树上进行 dfs，每遇到一个点就把这个点所代表的所有字符串的 w 之和加入当前答案中，dfs 到所有叶子时即可求出答案。
但我们发现后面这个贡献并不好算。
假设当前节点为 u，它所代表的所有字符串为 S[i,n] 的所有右端点在 [l,r] 内的前缀。
我们先找到 S[i,l] 在后缀自动机上代表的节点 v。此时的一个想法就是从 v 开始沿出边不断往后跳。后缀自动机对 endpos 比较友好，每一个节点上所有字符串的 w 都是一样的。因此我们只需要把所有跳到节点的 w 求和即可。
但直接这样做复杂度还是爆炸。这里有一个非常关键的 observation：在计算一个节点 u 的贡献的过程中，除了最后一个点之外，所有经过的点的出边都只有恰好一条，而且最后一个点至少有两条出边。证明很显然。
因此我们只需要在后缀自动机上预处理每一个节点到下一个至少有两条出边的节点的路径上的 w 之和即可。这个很容易在 O(n) 时间内解决。
关于如何的定位 S[i,l] 在后缀自动机上代表的节点 v，实际上我们也可以利用上面这个结构，只需要预处理每一个节点的下一个至少有两条出边的节点即可。与刚才的类似，也可以 O(n) 解决。
一些对基本子串结构的理解。
固定字符串 a。定义两个字符串 b_1,b_2 “同时出现”当且仅当存在一个字符串 b，满足 b_1,b_2 都是 b 的子串，并且 |endpos(b)|=|endpos(b_1)|=|endpos(b_2)|。
显然，“同时出现”关系是一种等价关系。我们考虑分析其中每一个等价类的形态。
对于一个等价类 S，\exists b\in S,\forall b_1\in S,b_1 是 b 的子串，并且 b_1 只在 b 中出现一次，否则与 b_1\in S 矛盾。
设 b_1=b[l\dots r]。我们将 b_1 写在矩阵的第 l 行第 r 列处。
那么 S 就会形成一个右上阶梯，即由 一条从左上到右下的路径 和 矩阵的右上边界 围成的区域。这便是基本子串结构。
如何显式地求出这个结构呢？其实很简单。
先建出后缀自动机。对于 DAG 上的一条边 (u,v)，如果 u,v 所对应的 endpos 集合大小相同（此时 u 一定只有一条出边），那么就将这条边标记为关键边。
如果只保留关键边，那么每个点入度和出度都至多为 1，因此我们得到了若干条关键链。对于每一条关键链，依次考虑链上的每个节点，第 i 个节点对应右上阶梯的第 i 列。
通过这种方法就可以显示地表示出这个阶梯的形状，时间复杂度 O(n)。
利用这个结构，我们可以解决一些只用一般后缀数据结构无法解决的问题。
回文划分计数。
首先回文后缀有一个很好的性质：可以划分为 O(\log n) 个等差数列。
设 dp_i 表示 S[1,i] 的方案数。
建出回文自动机来对于每一个 i 找出所有 S[1,i] 的回文后缀。
考虑 dp_i 的转移中的某一个等差数列。设其首项为 x，公差为 d，则在 dp_{i-d} 中已经计算了大部分值，只需要加入 dp_{i-x} 这一项即可。同时我们可以发现，在 (i-d,i) 之间的所有 dp 值都不会因这个等差数列中的串产生转移。
因此我们在回文树上的每一个节点记录一个值，表示上一次计算这个节点时的答案，每次只需要 O(1) 更新一下即可。时间复杂度 O(n\log n)。