SAM详解2(初级应用)

SAM

5. 初级应用

• 记 $longest(x)$ 为点 $x$ 代表子串集合中最长串的长度。
• 记 $shortest(x)$ 为点 $x$ 代表子串集合中最短串的长度。
• 记 $s{z}_x$ 为点 $x$ 代表的 $edp$ 的大小。
• 可能用 $len(x),le{n}_x,x.len$ 表示点 $x$ 所代表子串集合中最长串的长度，$link$ 等也是这样。
• 其他定义和 SAM详解1一样。

5.1 静态本质不同子串个数

在 parent tree 上，每个节点的 $edp$ 集合不同，即代表的子串不同。

则显然有 $ans={\sum }_{i=1}longest(i)-shortest(i)+1$

然后有 $shortest(i)=longest(f{a}_i)+1$，其中 $f{a}_i$ 为 $i$ 的父节点。

替换，则有 $ans={\sum }_{i=1}longest(i)-longest(f{a}_i)$，或者 $ans$