Prinzessin der Verurteilung：最短未出现字符串的板子。
思路
考虑在 SAM 上 dp，定义 \(dp_i\) 表示从 \(i\) 节点走到 NULL 节点所花费的最少步数。显然我们建出反图，跑 DAG 上 dp 即可。转移如下：
\[dp_i=1+\min_{j=1}^{|v_i|}dp_{v_{i,j}} \]输出方案的话记录下每个 dp 值的先驱，最后从 \(1\) 号节点开始遍历一遍即可。
注意，如果某个节点某个字母的转移边不存在的话，也需要建边，可以用一个超级源点 \(0\) 把这些 SAM 上不存在的边记录下来，这样才能算出不在里面出现过的字符串。
时间复杂度 \(O(tn|\sum|)\)，应该是最优复杂度了。
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define lc (p<<1)
#define rc ((p<<1)|1)
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
int n,len[2005],fa[2005],ch[2005][26],tot=1,np=1,rd[2005];
char s[1005];
vector<pi>g[2005];
struct node{
int v=0x3f3f3f3f,frm=-1,cx=-1;
}dp[2005];
void init()
{
for(int i=0;i<=tot;i++)
{
len[i]=fa[i]=0;
for(int j=0;j<26;j++)ch[i][j]=0;
dp[i]={0x3f3f3f3f,-1,-1};
rd[i]=0;
g[i].clear();
}
tot=np=1;
}
void extend(int c)
{
int p=np;
np=++tot;
len[np]=len[p]+1;
for(;p&&ch[p][c]==0;p=fa[p])ch[p][c]=np;
if(p==0)fa[np]=1;
else
{
int q=ch[p][c];
if(len[q]==len[p]+1)fa[np]=q;
else
{
int nq=++tot;
len[nq]=len[p]+1;
fa[nq]=fa[q],fa[q]=nq,fa[np]=nq;
for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
}
}
}
void outp()
{
int p=1;
while(p!=-1)
{
int v=dp[p].frm,c=dp[p].cx;
if(c<0)break;
cout<<char(c+'a');
p=v;
}
cout<<'\n';
}
void solve()
{
cin>>n>>s+1;
init();
for(int i=1;i<=n;i++)extend(s[i]-'a');
for(int i=1;i<=tot;i++)
{
for(int j=0;j<26;j++)
{
int v=ch[i][j];
g[v].push_back({i,j});
rd[i]++;
}
}
queue<int>q;
for(int i=0;i<=tot;i++)
{
if(rd[i]==0)
{
dp[i]={1,-1,-1};
q.push(i);
}
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(auto ed:g[u])
{
int v=ed.fi,c=ed.se;
rd[v]--;
if(rd[v]==0)q.push(v);
int dpv=dp[u].v+1;
if(dpv<dp[v].v)
{
dp[v].v=dpv;
dp[v].frm=u;
dp[v].cx=c;
}
else if(dpv==dp[v].v&&dp[v].cx>c)
{
dp[v].frm=u;
dp[v].cx=c;
}
}
}
outp();
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}