博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[NOI2018]你的名字
阅读量:5744 次
发布时间:2019-06-18

本文共 2219 字,大约阅读时间需要 7 分钟。

SAM写的太不熟练了~~SAM上的线段树合并也不熟练~~~

调了半天样例

题目大意:

给定一个S,Q次询问,每次给出T,l,r,

求对于S[l,r],属于T的子串却不属于S[l,r]的子串有多少个

看上去挺简洁的一个问题。。。

暴力68pts

对于S[1,n]68pts?

如果做过

 

就好做多了!

可以对A,B分别建SAM

拓扑排序找到A中每个点的后面路径条数。

然后在A上面匹配一遍,如果B匹配不出,直接加上A后面的路径条数

100pts?

刚才的暴力方法实际上不适用了

因为DAG根本无法精确找到[l,r]的部分。。

 

换一个角度

不从图的路径角度考虑子串了

直接从子串定义考虑

 

考虑,对于T,[1,i]这个前缀贡献的答案

假设同一个子串可以算多次的话

把[1,i]这个前缀在S[l,r]中匹配,设最长长度是mx

那么贡献的答案就是i-mx

 

怎么计算"把[1,i]这个前缀在S[l,r]中匹配"得到的最长后缀长度?

用线段树合并维护S的SAM中,点P的right集合

设[1,i-1]匹配的长度为now,匹配在SAM上的点为p

如果p有c出点,出点是x

如果x的right集合中有[l+now,r]区间中一个元素,意味着可以直接匹配下去,得到最长的长度了。break

否则now--,继续尝试。如果now==len[fa[p]],可以更新到更大的集合了,p=fa[p]

设i前缀匹配长度为lim[i]

 upda:2019.3.8:

这个匹配本质上是不断找到当前可能的最长后缀now+'c'在S中所有出现位置,然后看这些出现位置有没有末尾在[l+now,r]的

 

至于相同的子串是1个

那么对T串再建立SAM,用parent树去重,parent树上dfs,每个点的贡献是max(0,min(len[x]-len[fa[x]],len[x]-lim[x]))

相当于把同构的串放在一起,只计算一次

代码

注意,

1.线段树合并还要支持之后的查询

所以必须每次新建节点

类似:

2.tot,cnt,num计数器很多别混(懒得namespace了)

#include
#define reg register int#define il inline#define mid ((l+r)>>1)#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x);}namespace Miracle{const int N=1e6+5;const int M=1e6+5;int n,q;char s[N];int lim[M];ll ans;struct SAMSAM{ int ch[N][26]; int len[N],nd,fa[N]; int cnt; void init(){ cnt=1,nd=1; } struct tr{ int ls,rs; int sum; }t[N*20]; int rt[N]; int tot; void pushup(int x){ t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum; } void upda(int &x,int l,int r,int to){ x=++tot; if(l==r) { t[x].sum=1;return; } if(to<=mid) upda(t[x].ls,l,mid,to); else upda(t[x].rs,mid+1,r,to); pushup(x); } int merge(int x,int y,int l,int r){ // cout<<" merging "<
<<" "<
<<" :: "<
<<" "<
<
r) return 0; if(!x) return 0; if(L<=l&&r<=R) return t[x].sum; int ret=0; if(L<=mid) ret+=query(t[x].ls,l,mid,L,R); if(mid

总结:

SAM对于公共子串问题一个基本的方法是跑上去匹配

然后下来再考虑每个位置的贡献

parent树、DAG图无形对子串进行了同构的去重

 

转载于:https://www.cnblogs.com/Miracevin/p/10289785.html

你可能感兴趣的文章
webpack 4.0 中 clean-webpack-plugin 的使用
查看>>
POJ 2236 Wireless Network (并查集)
查看>>
python分类
查看>>
GitBlit (1)-- 在linux 安装 GitBlit 并运行
查看>>
程序是如何执行的(一)a=a+1
查看>>
18 已知下面的字符串是通过RANDOM随机数变量md5sum|cut-c 1-8截取后的结果
查看>>
BZOJ - 3578: GTY的人类基因组计划2
查看>>
爱——无题
查看>>
分布式服务框架原来与实践 读书笔记一
查看>>
【http】post和get请求的区别
查看>>
TFS强制撤销某个工作区的文件签出记录
查看>>
EL表达式无法显示Model中的数据
查看>>
ps6-工具的基础使用
查看>>
linux下使用过的命令总结(未整理完)
查看>>
时间助理 时之助
查看>>
英国征召前黑客组建“网络兵团”
查看>>
PHP 命令行模式实战之cli+mysql 模拟队列批量发送邮件(在Linux环境下PHP 异步执行脚本发送事件通知消息实际案例)...
查看>>
pyjamas build AJAX apps in Python (like Google did for Java)
查看>>
LAMP环境搭建1-mysql5.5
查看>>
centos5.9使用RPM包搭建lamp平台
查看>>