字符串

主要题意求字符串$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 ...

题意现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。 题解首先是广义后缀自动机，就是每次将$last$归为$Root$，从而将几个后缀自动机拼在一起处理 那么现在需要知道每个字串在$n$个母串中的出现次数，所谓字串，就是所有前缀的所有后缀，所以可以顺着前缀走，那么通过$Parent$树找后缀，一直往上跳，那么需要加一的所有后缀就是所属母串并非当前母串的那几个 此时再整理出每个所属母串个数$Size >= K$的初始贡献，即$Len[i] - Len[Father[i]]$，反之赋$0$ 又子串为前缀的后缀，那么一个节点的贡献即为它祖先至它本身的贡献前缀和，即它所有后缀能够构成的子串数 最后再遍历一遍前缀统计答案即可 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879 ...