有一个关于后缀自动机的问题

回复帖子

@卖报纸就找我 2020-02-14 18:39 回复

rt,最近看到这样一段代码但看不懂是啥意思可以帮忙解释下吗

  for (int i=1;i<=sz;i++) b[mx[i]]++;
        for (int i=1;i<=sz;i++) b[i]+=b[i-1];
        for (int i=sz;i>=1;i--) a[b[mx[i]]--]=i;
        for (int i=sz;i>=2;i--)
        {
            int x=a[i],F=fa[x];
            size[F]+=size[x];
            rig[F]=!rig[F]?rig[x]:rig[F];
            son[F][s[rig[x]-mx[F]]]=x;
        }
@ix35  2020-02-14 18:48 回复 举报

前面是桶排,后面是做了个 DP,没有上下文怎么知道什么意思?

@iostream  2020-02-14 20:29 回复 举报

首先按照 mx 降序排序,后面先是算了树上每个人的子树大小,然后每个人的 right 集合中随便选了一个,然后建出来了后缀树。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。