后缀自动机

后缀数组在文本串中寻找子串在文本串 $T$ 中寻找模式串 $S$，那么 $S$ 一定是 $T$ 的某个后缀的前缀，后缀排序后，在 $SA$ 中二分 $S$ 的位置，每次 $check$ 比较时间 $O (|S|)$，总时间复杂度 $O (|S| \log |T|)$ 比较两个子串的大小关系比较 $S$ 的子串 $A = S[l_1…r_1], B = S[l_2…r_2]$ 的大小关系 若 $lcp (l_1, l_2) \ge \min (|A|, |B|)$，则 $A < B \Longleftrightarrow |A| < |B|$，反之 $A < B \Longleftrightarrow rk_{l_1} < rk_{l_2}$ 本质不同子串数目设字符串 $S$ 长度为 $n$ $ans = \frac{n(n + 1)}2 - \sum\limits_{i = 2}^n height[i]$ 从字符串首或尾取字符构成最小字典序的字符串[USACO07DEC]Best Cow Line G 最基本贪心，若两端字符不同，优先取大的，那么问题就在于两端相 ...

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