分析:
其实我们可以很容易的想到,如果一个串是另一个串的子串,那么必定长的那个串不可能是字典序最小的串。其次,如果一个串为了使他成为字典序最小的串儿出现了矛盾的情况,那么也不可能是字典序最小的串。那么,按照规则建出trie树,之后在枚举每个字符串,在枚举的同时建图,判断是否有环,用拓扑排序解决。
附上代码:
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
#define N 30005
struct node
{
int son[27],flag;
}a[N*10];
struct no
{
int to,next;
}e[N];
int head[30],cnt,ans[N],in1[N],tot=1,n;
char s[N][305];
void add(int x,int y)
{
e[cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt++;
in1[y]++;
}
void insert(int x)
{
int rt=1;
int len=strlen(s[x]);
for(int i=0;i<len;i++)
{
int idx=s[x][i]-'a'+1;
if(!a[rt].son[idx])a[rt].son[idx]=++tot;
rt=a[rt].son[idx];
}
a[rt].flag=1;
}
bool tsort()
{
queue <int>q;
for(int i=1;i<=26;i++)if(!in1[i])q.push(i);
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i!=-1;i=e[i].next)
{
int to1=e[i].to;
in1[to1]--;
if(!in1[to1])q.push(to1);
}
}
for(int i=1;i<=26;i++)if(in1[i])return 0;
return 1;
}
bool check(int x)
{
int rt=1;
int len=strlen(s[x]);
for(int i=0;i<len;i++)
{
if(a[rt].flag)return 0;
int idx=s[x][i]-'a'+1;
for(int j=1;j<=26;j++)
{
if(j!=idx&&a[rt].son[j])add(idx,j);
}
rt=a[rt].son[idx];
}
return tsort();
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",&s[i]);
insert(i);
}
for(int i=1;i<=n;i++)
{
memset(head,-1,sizeof(head));
memset(in1,0,sizeof(in1));cnt=0;
if(!check(i))continue;
ans[++ans[0]]=i;
}
printf("%d\n",ans[0]);
for(int i=1;i<=ans[0];i++)
{
printf("%s\n",s[ans[i]]);
}
return 0;
}