Loading...

洛谷 P4070 [SDOI2016]生成魔咒

check评论:0 条 remove_red_eye浏览量:56 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-11-20

链接

建立后缀自动机,显然每个点的贡献就是$maxlen(i)-minlen(i)+1$,即以他结尾的子串的个数

然后这玩意根据性质,可以化作$maxlen(i)-maxlen(fa[i])$

$insert$的时候算贡献即可

$SAM$的锅这两周内一定补.webp

#include <bits/stdc++.h>
using namespace std;
long long ans=0;
struct SAM
{
    int fa[200020],len[200010],tot=1,las=1;
    map<int,int> ch[200010];
    void ins(int u)
    {
        int p=las;
        int np=las=++tot;
        len[np]=len[p]+1;
        for(;p&&!ch[p][u];p=fa[p])
        {
            ch[p][u]=np;
        }
        if(!p)
        {
            fa[np]=1;
        }
        else
        {
            int q=ch[p][u];
            if(len[q]==len[p]+1)
            {
                fa[np]=q;
            }
            else
            {
                int nq=++tot;
                fa[nq]=fa[q],ch[nq]=ch[q];
                len[nq]=len[p]+1;
                fa[q]=fa[np]=nq;
                for(;p&&ch[p][u]==q;p=fa[p])
                {
                    ch[p][u]=nq;
                }
            }
        }
        ans+=(long long)(len[np]-len[fa[np]]);
    }
}A;
int n,x;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        A.ins(x);
        cout<<ans<<"\n";
    } 
}

deco 没有放弃

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名