hihoCoder后缀自动机五题

发表于 | 分类于 |

重复旋律5

  1. 链接

    后缀自动机二·重复旋律5

  2. 题意

    给定一个串，求这个串的本质不同的子串个数。

  3. 题解

    1. 后缀数组

      答案就是 $ \sum_{i=1}^{n} n-sa[i]-height[i]+1 $

    2. 后缀自动机

      题目所求即 $ \sum_{i=1}^{cnt} siz[i] $

      按照逆拓扑序递推一遍即可。

  4. 核心代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void calc()
    {
        int mxval=0;
        for(int i=1;i<=cnt;i++)
            sum[mx[i]]++,mxval=max(mxval,mx[i]);
        for(int i=1;i<=mxval;i++)
            sum[i]+=sum[i-1];
        for(int i=1;i<=cnt;i++)
            tp[sum[mx[i]]--]=i;
        for(int i=cnt;i>=1;i--)
        {
            siz[par[tp[i]]]+=siz[tp[i]];
            ans[mx[tp[i]]]=max(ans[mx[tp[i]]],siz[tp[i]]);
        }
        for(int i=n-1;i>=1;i--)
            ans[i]=max(ans[i],ans[i+1]);
    }

(未完待补)