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$