Open CTP314 opened 5 years ago
https://ctp314.github.io/2019/07/05/BZOJ1396-%E8%AF%86%E5%88%AB%E5%AD%90%E4%B8%B2/
[BZOJ1396]识别子串 求字符串每个位置被包含且出现只有一次的最短子串长度 $SAM$ 部分很好想，关键是如何用线段树维护，我们假设当前位置为 $r$，对应的 $np$ 节点为 $x$，则有左端点 $l\ =\ r-maxlen(parent(x))$ 在区间 $[l,\ r]$ 内最小值为 $maxlen(parent(x))+1$ 并且对于区间 $[1,\ l-1]$ 每个位置 $i$
https://ctp314.github.io/2019/07/05/BZOJ1396-%E8%AF%86%E5%88%AB%E5%AD%90%E4%B8%B2/
[BZOJ1396]识别子串 求字符串每个位置被包含且出现只有一次的最短子串长度 $SAM$ 部分很好想，关键是如何用线段树维护，我们假设当前位置为 $r$，对应的 $np$ 节点为 $x$，则有左端点 $l\ =\ r-maxlen(parent(x))$ 在区间 $[l,\ r]$ 内最小值为 $maxlen(parent(x))+1$ 并且对于区间 $[1,\ l-1]$ 每个位置 $i$