给定一个初始字符串,要求支持两种操作,往字符串后加一个字符串和求一个字符串的出现次数。
可以对字符串建后最自动机,那么一个子串x的出现次数就是|right(x)|, |right(x)|可以用fail树维护。 那么每次往字符串后面加字符串,暴力维护|right(x)|时间复杂度会被卡成O(n^2)。 这时候就要用LCT来维护了
所以复杂度就变成O(nlogn)
(虽然感觉LCT的复杂度很玄学,但确实是logn啊…..)
#include <cstdio>#include <cstring>#include <string>#include <iostream>#define N 2000010using namespace std;int n,Mask;char Man[N],op[10];inline char C(){ static char buf[100000],*p1=buf,*p2=buf; if(p1==p2){ p2=(p1=buf)+fread(buf,1,100000,stdin); if(p1==p2) return EOF; } return *p1++;} inline void reaD(int &x){ char Ch=C();x=0; for(;Ch>'9'||Ch<'0';Ch=C()); for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=C());}inline void reaD(char *x){ char Ch=C();int len=0; for(;Ch>'Z'||Ch<'A';Ch=C()); for(;Ch>='A'&&Ch<='Z';x[len++]=Ch,Ch=C()); x[len]=0;}inline void swap(int &x,int &y){int z=x;x=y;y=z;}struct SAM_LCT{ int next[N][26],stp[N],f[N],ch[N][2],v[N],p,cnt,sta[N],tp,fail[N],add[N]; bool rev[N]; int isr(int x){return ch[f[x]][0]!=x&&ch[f[x]][1]!=x;} int isl(int x){return ch[f[x]][1]==x;} void pushdown(int x){ if(!x) return; if(add[x]!=0){ v[x]+=add[x]; if(ch[x][0])add[ch[x][0]]+=add[x]; if(ch[x][1])add[ch[x][1]]+=add[x]; add[x]=0; } if(!rev[x]) return; swap(ch[x][0],ch[x][1]); if(ch[x][0]) rev[ch[x][0]]^=1; if(ch[x][1]) rev[ch[x][1]]^=1; rev[x]=0; } void rot(int x){ int y=f[x],z=f[y],lor=isl(x); if(!isr(y)) ch[z][ch[z][1]==y]=x;f[x]=z; if(ch[y][lor]=ch[x][lor^1])f[ch[y][lor]]=y; f[ch[x][lor^1]=y]=x; } void splay(int x){ sta[tp=1]=x; for(int i=x;!isr(i);i=f[i]) sta[++tp]=f[i]; for(;tp;--tp) pushdown(sta[tp]); for(;!isr(x);rot(x))if(!isr(f[x])) rot(isl(f[x])^isl(x)?x:f[x]); } void access(int x){ int t=0; for(;x;t=x,x=f[x]) splay(x),ch[x][1]=t; } void reverse(int x){access(x);splay(x);rev[x]^=1;} void link(int x,int y){reverse(x);f[x]=y;splay(x);} void cut(int x,int y){reverse(x);access(y);splay(y);ch[y][0]=f[x]=0;} SAM_LCT(){p=cnt=1;} void Extend(int x){ x-='A'; int np=++cnt;stp[np]=stp[p]+1; while(p&&!next[p][x]) next[p][x]=np,p=fail[p]; if(!p) link(np,1),fail[np]=1; else{ int q=next[p][x]; if(stp[q]==stp[p]+1) link(np,q),fail[np]=q; else{ int nq=++cnt;stp[nq]=stp[p]+1; memcpy(next[nq],next[q],sizeof(next[q])); cut(q,fail[q]);link(nq,fail[q]);fail[nq]=fail[q]; link(q,nq);link(np,nq);fail[q]=fail[np]=nq; while(p&&next[p][x]==q) next[p][x]=nq,p=fail[p]; v[nq]=v[q]; } } p=np; reverse(1); access(p);splay(p);add[p]++; } void query(char *s){ int k=1,ok=0; for(int i=0;s[i];i++){ if(!next[k][s[i]-'A']) {ok=1;break;} else k=next[k][s[i]-'A']; } if(ok) puts("0"); else access(k),splay(k),PRintf("%d/n",v[k]),Mask^=v[k]; }}SAM;void decode(char *a,int mask){ int len=0; for(int i=0;a[i];i++,len++); for(int i=0;a[i];i++){ mask=(mask*131+i)%len; swap(a[i],a[mask]); }}int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); reaD(n); reaD(Man); for(int i=0;Man[i];i++) SAM.Extend(Man[i]); for(int i=1;i<=n;i++){ reaD(op);reaD(Man);decode(Man,Mask); if(op[0]=='A') for(int j=0;Man[j];j++) SAM.Extend(Man[j]); else SAM.query(Man); } return 0;}新闻热点
疑难解答