【题意】
【分析】
考虑把字符串建立在一个Trie树上,对应操作如下:
1.查看是否有这个儿子,没有就新建一个节点
2.向上跳到fa节点
3.当前节点标记为第i个字符串的末尾
4.标记为不可通配符也就是说最长公共前缀限制到这一位之前,所以所有的删除操作的min-1位置为公共前缀的最大值,撤销就相当于删除个位置,我们可以用set维护一下每个字符串中的最小值即可
5.最长公共前缀就相当于是两个串末尾节点在Trie树上的lca深度,记得和两个字符串的set中min值-1取一个min即可
【代码】
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=5e5+5; int n,ch[maxn][26],now=1,tot=1; int fa[maxn][19],dep[maxn]; int id[maxn],cnt,pt[maxn]; set <int> G[maxn]; int getlca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=18;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; if(x==y) return x; for(int i=18;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } int main() { freopen("typewriter.in","r",stdin); freopen("typewriter.out","w",stdout); // printf("11"); scanf("%d",&n); int opt,x,y; char s[2]; // printf("%d\n",n); for(int i=1;i<=n;i++) { scanf("%d",&opt); // printf("%d\n",opt); if(opt==1) { getchar(); int dig=getchar()-'a'; if(!ch[now][dig]) { ch[now][dig]=++tot; fa[tot][0]=now; for(int j=1;j<=18;j++) fa[tot][j]=fa[fa[tot][j-1]][j-1]; dep[tot]=dep[now]+1; } now=ch[now][dig]; } if(opt==2) now=fa[now][0]; if(opt==3) id[++cnt]=i; if(opt==4) { scanf("%d%d",&x,&y); if(G[x].count(y)) G[x].erase(y); else G[x].insert(y); } if(opt==5) { scanf("%d%d",&x,&y); // printf("yes %d %d\n",x,y); int ans=dep[getlca(pt[id[x]],pt[id[y]])]; if(G[x].size()) ans=min(ans,*G[x].begin()-1); if(G[y].size()) ans=min(ans,*G[y].begin()-1); printf("%d\n",ans); } pt[i]=now; } return 0; }