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图无形对子串进行了同构的去重