数据结构

主要题意求字符串$S$与$T$不同的子串总数 题解先考虑$l = 1, r = |T|$的情况： 因为任意子串为字符串前缀的某些后缀，那么令$Lim[i]$表示$T[1…i]$在$S$上所能匹配的最大长度，$Posi[i]$表示$T$的后缀自动机上的点$i$的$endpos$集合中最靠前的位置，那么答案即为 $$Ans = \sum\limits_{i = 1}^{nodes} \max (0, Len[i] - min (Len[Father[i]], Lim[Posi[i]]))$$ 接下来考虑$l, r$任意的情况： 原来能否在$S$的后缀自动机上往下走的判断依据只有当前节点是否存在$c$边，那么有了$l, r$的限制，就多需要判断向下的这个节点的$endpos$是否有存在于$[l + len, r]$（$len$表示已匹配长度）区间的位置，$endpos$集合用动态开点线段树维护一下就好了 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 ...