[BZOJ2555][LCT][后綴自動機]SubString

2019-11-14 08:57:45

字體：大中小

來源：轉載

供稿：網友

題意

給定一個初始字符串，要求支持兩種操作，往字符串后加一個字符串和求一個字符串的出現次數。

所以復雜度就變成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),