企业网站的最高形态是综合型网站,网站环境搭建好后怎么做网站,网络策划是什么,品牌营销理论有哪些SAM写的太不熟练了~~SAM上的线段树合并也不熟练~~~ 调了半天样例 题目大意#xff1a; 给定一个S#xff0c;Q次询问#xff0c;每次给出T#xff0c;l,r, 求对于S[l,r]#xff0c;属于T的子串却不属于S[l,r]的子串有多少个 看上去挺简洁的一个问题。。。 暴力68pts 对于S…SAM写的太不熟练了~~SAM上的线段树合并也不熟练~~~ 调了半天样例 题目大意 给定一个SQ次询问每次给出Tl,r, 求对于S[l,r]属于T的子串却不属于S[l,r]的子串有多少个 看上去挺简洁的一个问题。。。 暴力68pts 对于S[1,n]68pts 如果做过 [HEOI2015]最短不公共子串 就好做多了 可以对AB分别建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集合中有[lnow,r]区间中一个元素意味着可以直接匹配下去得到最长的长度了。break 否则now--继续尝试。如果nowlen[fa[p]]可以更新到更大的集合了pfa[p] 设i前缀匹配长度为lim[i] upda:2019.3.8: 这个匹配本质上是不断找到当前可能的最长后缀nowc在S中所有出现位置然后看这些出现位置有没有末尾在[lnow,r]的 至于相同的子串是1个 那么对T串再建立SAM用parent树去重parent树上dfs每个点的贡献是max(0,min(len[x]-len[fa[x]],len[x]-lim[x])) 相当于把同构的串放在一起只计算一次 代码 注意 1.线段树合并还要支持之后的查询 所以必须每次新建节点 类似CF666E Forensic Examination 2.totcntnum计数器很多别混懒得namespace了 #includebits/stdc.h
#define reg register int
#define il inline
#define mid ((lr)1)
#define numb (ch^0)
using namespace std;
typedef long long ll;
il void rd(int x){char ch;x0;bool flfalse;while(!isdigit(chgetchar()))(ch-)(fltrue);for(xnumb;isdigit(chgetchar());xx*10numb);(fltrue)(x-x);
}
namespace Miracle{
const int N1e65;
const int M1e65;
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(){cnt1,nd1;}struct tr{int ls,rs;int sum;}t[N*20];int rt[N];int tot;void pushup(int x){t[x].sumt[t[x].ls].sumt[t[x].rs].sum;}void upda(int x,int l,int r,int to){xtot;if(lr) {t[x].sum1;return;}if(tomid) upda(t[x].ls,l,mid,to);else upda(t[x].rs,mid1,r,to);pushup(x);}int merge(int x,int y,int l,int r){// cout merging x y :: l rendl;if(!x||!y) return xy;int idtot;if(lr){t[id].sumt[y].sumt[x].sum;return id;}t[id].lsmerge(t[x].ls,t[y].ls,l,mid);t[id].rsmerge(t[x].rs,t[y].rs,mid1,r);pushup(id);return id;}void ins(int c,int l){int pnd;len[ndcnt]l;upda(rt[cnt],1,n,l);for(;pch[p][c]0;pfa[p]) ch[p][c]cnt;// coutpp p cnt cnt char c ll l : ch[1][c]endl;if(!p){fa[cnt]1;return;}int qch[p][c];if(len[q]len[p]1){fa[cnt]q;return;}len[cnt]len[p]1;fa[cnt]fa[q];fa[q]fa[nd]cnt;for(reg j0;j26;j) ch[cnt][j]ch[q][j];for(;pch[p][c]q;pfa[p]) ch[p][c]cnt;}struct edge{int nxt,to;}e[2*N];int hd[2*N],num;void add(int x,int y){e[num].nxthd[x];e[num].toy;hd[x]num;}void build(){// cout cnt cntendl;for(reg i2;icnt;i){// couti : fafa fa[i]endl;add(fa[i],i);}}void dfs(int x){// cout xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx x rt rt[x] sz t[x].sumendl;for(reg ihd[x];i;ie[i].nxt){int ye[i].to;dfs(y);rt[x]merge(rt[x],rt[y],1,n);}}int query(int x,int l,int r,int L,int R){// cout xx x l and r : query L R sz t[x].sumendl;if(lr) return 0;if(!x) return 0;if(LlrR) return t[x].sum;int ret0;if(Lmid) retquery(t[x].ls,l,mid,L,R);if(midR) retquery(t[x].rs,mid1,r,L,R);return ret; }
}SAM;
struct samsam{int ch[M][26];int len[M],nd,fa[M];int mx[M];int cnt;void init(){cnt1,nd1;}void ins(int c,int l){int pnd;len[ndcnt]l;mx[cnt]lim[l];//warning!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!for(;pch[p][c]0;pfa[p]) ch[p][c]cnt;if(!p){fa[cnt]1;return;}int qch[p][c];if(len[q]len[p]1){fa[cnt]q;return;}len[cnt]len[p]1;fa[cnt]fa[q];fa[q]fa[nd]cnt;for(reg j0;j26;j) ch[cnt][j]ch[q][j];for(;pch[p][c]q;pfa[p]) ch[p][c]cnt;}struct edge{int nxt,to;}e[2*N];int hd[2*N],num;void add(int x,int y){e[num].nxthd[x];e[num].toy;hd[x]num;}void build(){for(reg i2;icnt;i){add(fa[i],i);}}void dfs(int x){////ans ansnsnannsansansna asn ansfor(reg ihd[x];i;ie[i].nxt){int ye[i].to;dfs(y);mx[x]max(mx[x],mx[y]);}ansmax(0,min(len[x]-mx[x],len[x]-len[fa[x]]));}void clear(){for(reg i1;icnt;i){for(reg j0;j26;j){ch[i][j]0;}mx[i]0;len[i]0;hd[i]0;fa[i]0;}num0;cnt1;}
}sam;
void clear(){sam.clear();ans0;
}
int main(){scanf(%s,s1);nstrlen(s1);SAM.init();for(reg i1;in;i){SAM.ins(s[i]-a,i);}
// cout after ins endl;SAM.build();
// cout after build endl;SAM.dfs(1);
// cout after dfs endl;rd(q);int l,r;while(q--){clear();scanf(%s,s1);rd(l);rd(r);int lenstrlen(s1);int now0,p1;for(reg i1;ilen;i){//pipei int cs[i]-a;while(1){// cout cc c SAM.ch[p][c]endl;if(SAM.ch[p][c]SAM.query(SAM.rt[SAM.ch[p][c]],1,n,lnow,r)){now;pSAM.ch[p][c];break;} if(!now) break;--now;if(nowSAM.len[SAM.fa[p]]) pSAM.fa[p];}lim[i]now;// cout lim i : lim[i] p pendl;}sam.init();for(reg i1;ilen;i){//insertsam.ins(s[i]-a,i);}ans0;sam.build();sam.dfs(1);printf(%lld\n,ans);}return 0;
}}
signed main(){Miracle::main();return 0;
}/*Author: *Miracle*Date: 2019/1/18 17:48:14
*/ 总结 SAM对于公共子串问题一个基本的方法是跑上去匹配 然后下来再考虑每个位置的贡献 parent树、DAG图无形对子串进行了同构的去重 转载于:https://www.cnblogs.com/Miracevin/p/10289785.html
