題目：https://www.lydsy.com/JudgeOnline/problem.php?id=3881
對 S 建 SAM ，每個 T 會讓 S 的 parent 樹的鏈并答案+1；在 T 走每一步的時候，走到的節點用 LCT access 一下，就能找到該點到 parent 根的鏈。
給鏈打標記。在 access 的過程中，如果遇到已經打過這個 T 標記的點，就停止 access 。
注意實現的時候，在判斷 fa[x] 有沒有標記之前要先 splay(fa[x]) 。
#include<cstdio> #include<cstring> #include<algorithm> #define ls c[cr][0] #define rs c[cr][1] using namespace std; int rdn() {int ret=0;bool fx=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return fx?ret:-ret; } const int N=1e5+5,M=2e6+5,K=26; int n,ps[N],tot=1,c[M][K],tc[M][K],fl[M],q[M]; int tim,dfn[M],fa[M],vl[M],tg[M],sta[M]; char s[M]; bool isrt(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;} void cz(int cr) {if(!tg[cr])return; int w=tg[cr];tg[cr]=0;vl[ls]+=w; vl[rs]+=w;tg[ls]+=w; tg[rs]+=w;dfn[ls]=dfn[rs]=dfn[cr];/// } void rotate(int x) {int y=fa[x],z=fa[y],d=(x==c[y][1]);if(!isrt(y))c[z][y==c[z][1]]=x;fa[x]=z; fa[y]=x; fa[c[x][!d]]=y;c[y][d]=c[x][!d]; c[x][!d]=y; } void splay(int x) {int top; sta[top=1]=x;for(int k=x;!isrt(k);k=fa[k])sta[++top]=fa[k];for(int i=top;i;i--)cz(sta[i]);for(int y=fa[x],z=fa[y];!isrt(x);rotate(x),y=fa[x],z=fa[y])if(!isrt(y))((y==c[z][0])^(x==c[y][0]))?rotate(x):rotate(y); } void access(int x) {splay(x); if(dfn[x]==tim)return;int t=0;while(1){c[x][1]=t;if(!fa[x]){ tg[x]++;vl[x]++;dfn[x]=tim;return;}splay(fa[x]);//splay firstif(dfn[fa[x]]==tim){ tg[x]++;vl[x]++;dfn[x]=tim;return;}t=x; x=fa[x];} } void link(int x,int y){ fa[y]=x;} int Ins() {int cr=1,len=strlen(s+1);for(int i=1;i<=len;i++){int w=s[i]-'a';if(!tc[cr][w])tc[cr][w]=++tot;cr=tc[cr][w];}return cr; } void get_fl() {int he=0,tl=0;for(int i=0,v;i<K;i++)if((v=tc[1][i])){q[++tl]=v;fl[v]=1;link(1,v);}else tc[1][i]=1;while(he<tl){int k=q[++he],pr=fl[k];for(int i=0,v;i<K;i++)if((v=tc[k][i])){ q[++tl]=v;fl[v]=tc[pr][i];link(tc[pr][i],v);}else tc[k][i]=tc[pr][i];} } void solve() {tim++; int cr=1,len=strlen(s+1);for(int i=1;i<=len;i++){cr=tc[cr][s[i]-'a'];access(cr);} } int main() {n=rdn();for(int i=1;i<=n;i++){ scanf("%s",s+1); ps[i]=Ins();}get_fl();int Q=rdn(),op,x;while(Q--){op=rdn();if(op==1){ scanf("%s",s+1); solve();}else{x=rdn(); x=ps[x];splay(x); printf("%d\n",vl[x]);}}return 0; }
?
