对于一个字符串 $S$，建立出它的 SAM，选择一个后缀树上的结点 $u$，令 $p=\min(\operatorname{endpos}(u))$．对于所有 满足 $(\operatorname{endpos}(u)$ 中所有 $\ge p$ 的数字 = $\operatorname{endpos}(v)$ 中所有 $\ge p$ 的数字) 的 $u$ 的祖先结点 $v$．对于每个 $v$ 取出 $\operatorname{endpos}(v)$ 中的最大的 $<p$ 的数字，去重，组成一个集合 $A$．$A$ 大小的最大是什么级别的？

写个伪代码就是：

fn (u: SamNode) {
  p = min(endpos(u));
  v = u;
  S = ∅;

  while 1 {
    if (!fa[v] || endpos[u].filter(|x| x>=p) != endpos[v].filter(|x| x>=p)) break;
    v = fa[v];
    S.insert(v.filter(|x| x<p).max());
  }

  return S.size();
}

你要构造一个字符串 S 然后选一个 node，最大化这个 fn 的结果．

这玩意我尝试构造了半天甚至没构造出明显优于随机串的，有没有大佬能帮一下．

随机串看似这东西是 log 级别的．

endpos 的定义见 OI Wiki．