【题解】喵星球上的点名广义 SAM –Kylin_xy

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

//先放上建立的代码和查询的代码, 插入写法和普通 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);
    }
//这就是第二问的计算

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

【题解】喵星球上的点名广义 SAM –Kylin_xy

于2020年1月5日2020年1月5日由Kylin_xy发布

Kylin_xy

2 条评论

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

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

回复 Kylin_xy 取消回复

【题解】喵星球上的点名 广义 SAM –Kylin_xy

于2020年1月5日2020年1月5日由Kylin_xy发布

Kylin_xy

2 条评论

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

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

回复 Kylin_xy 取消回复

【题解】喵星球上的点名广义 SAM –Kylin_xy