题目大意:n个字符串,m个操作,可以插入字符串,也可以询问某T个字符串的最长后缀
题解:Trie+lca
Trie树的插入与查询操作。把字符串反转就相当于求公共前缀。
lca的深度就是公共前缀的长度。
代码:
//biology include<iostream> #include<cstring> #include<cstdio> #define maxn 1000009 using namespace std; int js,n,m,cnt,pos[maxn],deep[maxn],trie[maxn][26],dad[maxn][26]; char s[maxn]; void insert(){ int root=0,len=strlen(s); for(int i=len-1;i>=0;i--){ int id=s[i]-'a'; if(trie[root][id]==0){ trie[root][id]=++cnt; deep[cnt]=deep[root]+1;dad[cnt][0]=root; for(int j=0;dad[cnt][j];j++)dad[cnt][j+1]=dad[dad[cnt][j]][j]; } root=trie[root][id]; } pos[js]=root; } int lca(int x,int y){ if(deep[x]>deep[y])swap(x,y); for(int i=20;i>=0;i--) {if(deep[dad[y][i]]>=deep[x])y=dad[y][i];} if(x==y)return x; for(int i=20;i>=0;i--){if(dad[x][i]!=dad[y][i])x=dad[x][i],y=dad[y][i];} return dad[x][0]; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%s",s);js++; insert(); } for(int i=1;i<=m;i++){ int od,t,p,q,L; scanf("%d",&od); if(od==1){ scanf("%s",s);js++; insert(); }else{ scanf("%d%d",&t,&p); for(int i=2;i<=t;i++){ scanf("%d",&q); if(i==2)L=lca(pos[p],pos[q]); else L=lca(L,pos[q]); } printf("%d ",deep[L]); } } return 0; }