C++(g++ 7.5.0) 解法, 执行用时: 112ms, 内存消耗: 26216K, 提交时间: 2022-10-10 17:10:36

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define _for(i,L,R) for(int i=L;i<=R;++i)
//#define int long long
  
using namespace std;

const int N=3e4+5,M=1e6+5;
string s[N];

class Node{
public:
	int ch[26];
	bool ed;
}tr[M];
int tot,g[26][26],in[26];

void insert(string s)
{
	int u=0;
	for(char x:s){
		int c=x-'a';
		if(!tr[u].ch[c]) tr[u].ch[c]=++tot;
		u=tr[u].ch[c];
	}
	tr[u].ed=1;
}

bool top_sort()
{
	queue<int> que;
	_for(i,0,25) if(!in[i]) que.push(i);
	while(que.size()){
		int u=que.front(); que.pop();
		_for(i,0,25) if(g[u][i]){
			if(--in[i]==0) que.push(i);
		}
	}
	_for(i,0,25) if(in[i]) return 0;
	return 1;
}

void solve()
{
	int n;
	scanf("%d",&n);
	_for(i,1,n) cin>>s[i],insert(s[i]);
	vector<string> vec;
	_for(i,1,n){
		memset(g,0,sizeof g);
		memset(in,0,sizeof in); 
		int u=0,ok=1;
		for(char x:s[i]){
			if(tr[u].ed) {ok=0;break;}
			int c=x-'a';
			_for(j,0,25) if(tr[u].ch[j] and j!=c and !g[c][j]) g[c][j]=1,in[j]++;
			u=tr[u].ch[c];
		}
		if(ok and top_sort()) vec.push_back(s[i]);
	}
	printf("%d\n",vec.size());
	for(auto s:vec) cout<<s<<"\n";
}

signed main()
{   
	int T = 1;
//	scanf("%d",&T);
	while(T--) solve();
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 244ms, 内存消耗: 25316K, 提交时间: 2019-05-31 19:51:17

#include<bits/stdc++.h>
using namespace std;
struct trie{int so[26];int we;}t[250010];
string s[30010];
int n,ro,num,na,an[30010],da[28];
void build(int &nu,int l,int we){
	if (!nu) nu=++num;
	if (l<s[we].length())build(t[nu].so[s[we][l]-'a'],l+1,we);
	else t[nu].we=we;
}
void dfs(int nu){
	if (t[nu].we){an[++na]=t[nu].we;return ;}
	vector<int> s1,s2;
	s1.clear();s2.clear();
	for (int i=0;i<26;i++){
		s1.push_back(da[i]);
		if (t[nu].so[i]!=0)s2.push_back(i);
	}
	for (auto i:s2){
		bool ne=1;
		for (auto j:s2)if (j!=i&&da[j]&(1<<i)) ne=0;
		if (ne){
			for (auto j:s2)if (j!=i){da[i]|=(1<<j);da[i]|=da[j];}
			for (int k=0;k<26;k++)if(da[k]&(1<<i))da[k]|=da[i];
			dfs(t[nu].so[i]);
			for (int k=0;k<26;k++)da[k]=s1[k];
		}
	}
}
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){cin>>s[i];build(ro,0,i);}
	dfs(1);
	sort(an+1,an+na+1);
	cout<<na<<endl;
	for (int i=1;i<=na;i++)cout<<s[an[i]]<<endl;;
	return 0;
}