这个题题面好可爱嘛~
那我们考虑简化一下~
第一问是求每个文本串中含有的模式串个数。
第二问是求每个模式串是多少个文本串的子串。
看到多串匹配肯定想到广义 $SAM$啦,所以我们建出广义 $SAM$,建立的同时标记 $size$,就是每次 $upd$的时候 $size[rt]++$;
第一问呢,直接把每个文本串扔到广义 $SAM$上跑一遍,跑完了输出 $size[rt]$就行了。
第二问呢,我们在做第一问的时候就要在跑完的时候把 $tag[rt]++$,就是标记一下这个位置会有一个文本串匹配到。然后依次查询每个模式串,每次 $ans$把沿途的 $tag[rt]$全部累加起来就可以啦。
完结撒花~
一个不知道对不对的理解:广义 $SAM$和 $SAM$的关系类似于可持久化 $Trie$树和 $Trie$树的关系。(如果大佬觉得不对请指正哦!)
代码比较简单啦~还是贴一下核心部分吧

//先放上建立的代码和查询的代码, 插入写法和普通 SAM 一样就不贴了。upd 就是建立,que 就是查询
il void upd(it x,it id){
    for(;x&&v[x]!=id;x=f[x]) v[x]=id,++sz[x];
}
il void que(it x,it id){
    for(;x&&v[x]!=id;x=f[x]) v[x]=id,ans+=tg[x];
}
//In 就是读入 ins 就是在 SAM 上面插入字符串
    for(i=1;i<=n;++i){
        In(len1[i]),lst=1;
        for(j=1;j<=len1[i];++j) In(nam[++now]),ins(nam[now]);
        In(len2[i]),lst=1;
        for(j=1;j<=len2[i];++j) In(nam[++now]),ins(nam[now]);
    }   
    now=0;
    for(i=1;i<=n;++i){
        rt=1;
        for(j=1;j<=len1[i];++j) upd(rt=t[rt][nam[++now]],i); 
        rt=1;
        for(j=1;j<=len2[i];++j) upd(rt=t[rt][nam[++now]],i);
    }
//我们先要把这个广义 SAM 建出来
    for(i=1;i<=m;++i){
        rt=1;
        In(now);while(now--) In(j),rt=t[rt][j]; 
        printf("%d\n",sz[rt]),++tg[rt];
    }
//这就是第一问的计算
    memset(v,0,sizeof(v));
    now=0;
    for(i=1;i<=n;++i){
        rt=1,ans=0;
        for(j=1;j<=len1[i];++j) que(rt=t[rt][nam[++now]],i);
        rt=1;
        for(j=1;j<=len2[i];++j) que(rt=t[rt][nam[++now]],i);
        printf("%d ",ans);
    }
//这就是第二问的计算

有错误请大佬批评指正吖!有问题请留言吖!

分类: 文章

Kylin_xy

萌新妹子刚学OI。

2 条评论

boshi · 2020年1月5日 8:07 下午

SAM 和广义 SAM 的区别,我个人感觉更类似于 KMP 和 AC 自动机的区别。

    Kylin_xy · 2020年1月5日 10:34 下午

    对对,这个比喻很贴切,谢谢大佬!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code