傳送門
題意簡述：
要求在線支持兩個(gè)操作
(1):在當(dāng)前字符串的后面插入一個(gè)字符串
(2):詢問字符串s在當(dāng)前字符串中出現(xiàn)了幾次？(作為連續(xù)子串)

---

思路：
考慮用$lct$來動(dòng)態(tài)維護(hù)$sam$的$right$集合。
代碼：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1200005;
char s[N];
int n;
string str;
inline void gets(int Mask){scanf("%s",s);str=s;for(ri i=0,up=str.size();i<up;++i){Mask=(Mask*131+i)%up;char t=str[i];str[i]=str[Mask];str[Mask]=t;}
}
int Mask=0;
namespace lct{int son[N][2],rev[N],siz[N],fa[N],add[N],stk[N],top=0;inline void pushnow(int p,int v){siz[p]+=v,add[p]+=v;}inline void pushdown(int p){if(add[p])pushnow(son[p][0],add[p]),pushnow(son[p][1],add[p]),add[p]=0;}inline bool isroot(int p){return !fa[p]||((p^son[fa[p]][0])&&(p^son[fa[p]][1]));}inline bool which(int p){return p^son[fa[p]][0];}inline void rotate(int x){int y=fa[x],z=fa[y],t=which(x);if(z&&!isroot(y))son[z][which(y)]=x;fa[y]=x,fa[x]=z,son[y][t]=son[x][t^1],son[x][t^1]=y;if(son[y][t])fa[son[y][t]]=y;}inline void splay(int x){stk[top=1]=x;for(ri p=x;!isroot(p);p=fa[p])stk[++top]=fa[p];while(top)pushdown(stk[top--]);	while(!isroot(x)){if(!isroot(fa[x]))rotate(which(x)^which(fa[x])?x:fa[x]);rotate(x);}}inline void access(int x){for(ri y=0;x;x=fa[y=x])splay(x),son[x][1]=y;}inline void link(int x,int y){fa[x]=y,access(y),splay(y),pushnow(y,siz[x]);}inline void cut(int x){access(x),splay(x),pushnow(son[x][0],-siz[x]),fa[son[x][0]]=0,son[x][0]=0;}
}
namespace sam{int son[N][26],len[N],Link[N],tot=1,last=1;inline void insert(int x){int p=last,np=++tot;lct::siz[np]=1,len[last=np]=len[p]+1;while(p&&!son[p][x])son[p][x]=np,p=Link[p];if(!p)return lct::link(np,Link[np]=1);int q=son[p][x],nq;if(len[q]==len[p]+1)return lct::link(np,Link[np]=q);len[nq=++tot]=len[p]+1,memcpy(son[nq],son[q],sizeof(son[nq]));lct::link(nq,Link[nq]=Link[q]);lct::cut(q);lct::link(np,Link[np]=nq);lct::link(q,Link[q]=nq);while(p&&son[p][x]==q)son[p][x]=nq,p=Link[p];}inline void init(){scanf("%s",s+1);for(ri i=1,up=strlen(s+1);i<=up;++i)insert(s[i]-'A');}inline void add(){gets(Mask);for(ri i=0,up=str.size();i<up;++i)insert(str[i]-'A');}inline int query(){gets(Mask);int p=1;for(ri i=0,up=str.size();i<up;++i)if(!(p=son[p][str[i]-'A']))return 0;return lct::splay(p),lct::siz[p];}
}
int main(){scanf("%d",&n),sam::init();while(n--){char op[6];scanf("%s",op);if(op[0]=='A')sam::add();else{int ret=sam::query();Mask^=ret,cout<<ret<<'\n';}}
}

轉(zhuǎn)載于:https://www.cnblogs.com/ldxcaicai/p/10582388.html

總結(jié)

以上是生活随笔為你收集整理的2019.03.01 bzoj2555: SubString（sam+lct）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。