先把所有串建成字典树 字典树上的边 边权为1
然后如果两个点 一个是另一个的后缀 那么就另一个向那一个连0的边
跑一通最小树形图就好了 我不会 拷了个板子
输出方案就很蛋疼了
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(char *s){
char c=nc(); int len=0;
for (;!(c>='a' && c<='z');c=nc());
for (;c>='a' && c<='z';s[++len]=c,c=nc()); s[++len]=0; return len-1;
}
const int INF=0x3f3f3f3f;
const int maxn=1000005;
int m;
struct Edge
{
int u,v,cost,id,ru,rv,rcost;
}edge[maxn];
int _u[maxn],_v[maxn];
void add_Edge(int id,int u,int v,int c)
{
edge[id].id=id;
edge[id].u=edge[id].ru=u;
edge[id].v=edge[id].rv=v;
edge[id].cost=edge[id].rcost=c;
_u[id]=u; _v[id]=v;
}
int pre[maxn],id[maxn],vis[maxn],in[maxn];
//// !!!!
int preid[maxn],useE[maxn];
int eA[maxn],eD[maxn];
int ex;
int zhuliu(int root,int n,int m)
{
int ex=m,res=0;
while(true)
{
for(int i=0;i<n;i++) in[i]=INF;
for(int i=0;i<m;i++)
{
if(edge[i].u!=edge[i].v&&edge[i].cost<in[edge[i].v])
{
pre[edge[i].v]=edge[i].u;
in[edge[i].v]=edge[i].cost;
//// !!!!
preid[edge[i].v]=edge[i].id;
}
}
for(int i=0;i<n;i++)
if(i!=root&&in[i]==INF) return -1;
int tn=0;
memset(id,-1,sizeof(id));
memset(vis,-1,sizeof(vis));
in[root]=0;
for(int i=0;i<n;i++)
{
res+=in[i];
int v=i;
//// !!!!
if(i!=root) useE[preid[i]]++;
while(vis[v]!=i&&id[v]==-1&&v!=root)
{
vis[v]=i; v=pre[v];
}
if(v!=root&&id[v]==-1)
{
for(int u=pre[v];u!=v;u=pre[u]) id[u]=tn;
id[v]=tn++;
}
}
if(tn==0) break;
for(int i=0;i<n;i++)
if(id[i]==-1) id[i]=tn++;
for(int i=0;i<m;i++)
{
int v=edge[i].v;
edge[i].u=id[edge[i].u];
edge[i].v=id[edge[i].v];
if(edge[i].u!=edge[i].v)
{
edge[i].cost-=in[v];
//// !!!!
eA[ex]=edge[i].id;
eD[ex]=preid[v];
edge[i].id=ex;
ex++;
}
}
n=tn;
root=id[root];
}
//// !!!!
for(int i=ex-1;i>=m;i--)
{
if(useE[i])
{
useE[eA[i]]++; useE[eD[i]]--;
}
}
return res;
}
const int N=55;
int n;
char s[N][15]; int len[N];
const int M=5005;
int ncnt=1;
int fat[M]; char c[M];
int ch[M][26];
inline void Ins(char *s,int n){
int p=1;
for (int i=1;i<=n;i++){
if (!ch[p][s[i]-'a']) ch[p][s[i]-'a']=++ncnt,fat[ncnt]=p,c[ncnt]=s[i];
p=ch[p][s[i]-'a'];
}
}
inline string Str(int p){
string s;
while (p!=1)
s=c[p]+s,p=fat[p];
return s;
}
inline bool Jud(string a,string b){
if (b.length()>a.length()) return 0;
int s=a.length()-b.length();
for (int i=0;i<b.length();i++)
if (a[s+i]!=b[i])
return 0;
return 1;
}
int Pre[M];
int _fat[M];
inline int Fat(int u){
return u==_fat[u]?u:_fat[u]=Fat(_fat[u]);
}
int w[M][M];
int idx[M];
int main(){
freopen("dictionary.in","r",stdin);
freopen("dictionary.out","w",stdout);
scanf("%d",&n);
ncnt=1;
for (int i=1;i<=n;i++)
len[i]=read(s[i]),Ins(s[i],len[i]);
for (int i=0;i<ncnt;i++)
for (int j=0;j<ncnt;j++)
w[i][j]=1<<30;
for (int i=2;i<=ncnt;i++)
add_Edge(m++,fat[i]-1,i-1,2),w[fat[i]-1][i-1]=1;
for (int i=2;i<=ncnt;i++)
for (int j=2;j<=ncnt;j++)
if (i!=j && Jud(Str(i),Str(j)))
add_Edge(m++,i-1,j-1,1),w[i-1][j-1]=0;
int ans=zhuliu(0,ncnt,m)+1;
for (int i=0;i<m;i++)
if (useE[i]&&edge[i].rcost)
Pre[_v[i]+1]=_u[i]+1;
for (int i=1;i<=ncnt;i++) _fat[i]=i;
for (int i=2;i<=ncnt;i++)
if (w[Pre[i]-1][i-1]==0)
_fat[Fat(i)]=Pre[i];
int tot=0;
for (int i=1;i<=ncnt;i++) if (Fat(i)==i) idx[i]=++tot;
printf("%d\n",tot);
printf("0\n");
for (int i=2;i<=ncnt;i++)
if (Fat(i)==i)
printf("%d %c\n",idx[Fat(fat[i])],c[i]);
return 0;
}