一段时间没打字符串相关的题了，找道简单的 Trie 练练手。

题意

题目链接。

维护一个复古打印机，支持添加字母，删除字母，打印字母。求用最小步骤打印出所需的所有单词。

解析

首先容易想到建 Trie，然后在 Trie 上进行 dfs，每次走到一个结点就添加这个结点对应的字母，若走到了一个单词的结尾就打印，然后在每层 dfs 返回之前删除当前字母。

但是这并不能满足最小步骤。先说结论：最长的单词最后打印。

思路及证明如下：

我们考虑最终操作序列中三种操作所占的数量。容易发现添加字母的操作是一定的（一定为结点数），同时打印操作也是一定的（一定为单词数）。我们考虑最小化删除操作的数量。

容易发现，最后打印的那个单词在 Trie 树上的一整条链是不用删除的。而删除操作的数量即为结点数减去这条链的长度，因此只需要这条链最长，即最后打印的单词最长即可，容易维护（详见下方代码）。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=25005;
int n,tree[N<<5][26];
int tot,cnt,Ans,maxx;
bool p[N<<5],tag[N<<5];
char s[50],ans[N<<7];
char S[50];
inline void insert(){
    scanf("%s",s);
    int len=strlen(s);
    int u=0;
    if(len>maxx){//记录最长单词
        maxx=len;
        for(int i=0;i<len;i++){
            S[i]=s[i];
        }
    } 
    for(int i=0;i<len;i++){
        int c=s[i]-'a';
        if(!tree[u][c]) tree[u][c]=++tot;
        u=tree[u][c];
    }
    p[u]=1;
}
inline void pre(){//预处理最长单词所在链
    int len=maxx;
    int u=0;
    for(int i=0;i<len;i++){
        int c=S[i]-'a';
        tag[tree[u][c]]=1;//tag 记录是否为最长单词所在链
        u=tree[u][c];
    }
}
inline void print(){
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++) printf("%c\n",ans[i]);
}
inline void dfs(int u){
    if(p[u]){//打印
        Ans++;
        ans[++cnt]='P';
        if(Ans==n) print();//为了防止进行多余的删除操作，在这里输出
    }
    for(int i=0;i<26;i++){
        if(tree[u][i]&&!tag[tree[u][i]]){
            ans[++cnt]='a'+i;
            dfs(tree[u][i]);
        }
    }
    for(int i=0;i<26;i++){
        if(tree[u][i]&&tag[tree[u][i]]){
            ans[++cnt]='a'+i;
            dfs(tree[u][i]);
        }
    }//先走其他的，最后走最长单词所在链
    if(u!=0) ans[++cnt]='-';
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) insert();
    pre();
    dfs(0);
    return 0;
}