题解：P10526 [XJTUPC2024] 命令行

· · 题解

题目链接：P10526 [XJTUPC2024] 命令行

理解题意之后，不难想到我们可以利用字典树来维护这些信息。

我们先将 \text{T} 操作放一边，对于剩下的操作而言，我们只需在字典树的模板下稍稍记录每次最后一个节点所代表的编号即可。

因此这题的难度其实是在 \text{T} 操作上，我们要思考如何得到一个最长前缀，关于这点我们可以利用类似链表跳转的思想来解决，我们可以将每个节点的父节点和其跳转到的节点求出来，对于跳转操作而言，如果该节点大小大于 1 的话我们需要不断向下遍历，直到子树大小刚好为 1，此时我们便令其父节点的跳转指向该节点，通俗点来说就是求出我们补全时需要跳到哪个字串。

当需要删除字符时，我们只需看看能否跳转到其父节点即可。

当存入的字符多于我们命令字符的长度时，我们要实时维护新节点的父节点。

解决以上问题后就可以快乐 coding 了！！！

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
const int N=1e6+10;

int n,m;
int t[N][30],fa[5*N],siz[N];
int id[N],nxt[N];
int idx=1;
char str[N*5];
char opt[N*5];

int read(char x){
    return x-'a';
}

void add(char str[],int x){
    int p=0,len=strlen(str);
    rep(i,0,len-1){
        int u=read(str[i]);
        if(!t[p][u]){
            t[p][u]=idx++;
            fa[t[p][u]]=p;
            siz[p]++;
        }
        p=t[p][u];
    }
    id[p]=x;
}

int ask(int p){
    return id[p]==0?-1:id[p];
}

void modify(int p){
    nxt[p]=p;
    if(siz[p]==1){
        rep(i,0,25){
            if(t[p][i]){
                modify(t[p][i]);
                if(!id[p])nxt[p]=nxt[t[p][i]];
                break;
            }
        }   
    }
    if(siz[p]>1){
        rep(i,0,25){
            if(t[p][i]){
                modify(t[p][i]);
            }
        }
    }
}

signed main(){
    scanf("%lld%lld",&n,&m);
    rep(i,1,n){
        cin>>str;
        add(str,i);
    }
    cin>>opt;
    modify(0);
    int now_id=0;
    rep(i,0,m-1){
        if(opt[i]=='E'){
            printf("%lld ",ask(now_id));
            now_id=0;
        }
        else if(opt[i]=='T'){
            if(nxt[now_id])now_id=nxt[now_id];
        }
        else if(opt[i]=='B'){
            now_id=(now_id!=0)?fa[now_id]:now_id;
        }
        else {
            if(now_id>=idx){
                fa[now_id+1]=now_id;
                now_id++;
            }
            else if(!t[now_id][read(opt[i])]){
                fa[idx]=now_id;
                now_id=idx;
            }
            else now_id=t[now_id][read(opt[i])];
        }   
    }
    return 0;
}