P10526 [XJTUPC2024] 命令行

#include<bits/stdc++.h>
using namespace std;
#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 cnt[N],idx;
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];cnt[p]++;
    }
    id[p]=x;
}

//int ask(char str[]){
//    int p=0,len=strlen(str);
//    int u;
//    rep(i,0,len-1){
//        u=read(str[i]);
//        if(!t[p][u])return -1;
//        p=t[p][u];
//    }
//    return 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]);
			}
		}
	}
}

int main(){
    scanf("%d%d",&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("%d ",(id[now_id]==0?-1:id[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)?0:fa[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;
}

WA 3