- 首先判断一下这个串是不是某个串的前缀
像s1 = ab 与 s2 =abb ,这里s1是s2的前缀,那么s2就一定不可以
- 判断一下优先级是否合法,
s1=ab,
s2=bb,
s3=aa
s1是一定不可以作为开头的,比较s1和s2的时候a>b,比较s1和s3的时候a<b
也就是自相矛盾了,所以不可以。
- 判断是否矛盾,用toposort就可以了
- 比较大小和判断前缀,可以用一个字典树进行维护
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int N=30,M=3e5+5;
vector<string>v1,v2;
int ch[M][N],tag[M],tot;
void insert(string s) {
int p=0;
for(int i=0;i<s.size();i++) {
int v=s[i]-'a'+1;
if(ch[p][v]==0)ch[p][v]=++tot;
p=ch[p][v];
}
tag[p]=1;//记录这里有一个串
}
int in[N];
vector<int>v[N];
bool topo() {//判断一下会不会自相矛盾
int ans=0;
queue<int>q;
for(int i=1;i<=26;i++)
if(in[i]==0)q.push(i);
while(!q.empty()) {
int now=q.front();
q.pop();
ans++;
for(auto x:v[now])
if(--in[x]==0)q.push(x);
}
return ans==26;
}
bool check(string s) {
for(int i=1;i<=26;i++)in[i]=0,v[i].clear();
int p=0;
for(int i=0;i<s.size();i++) {
int x=s[i]-'a'+1;
for(int j=1;j<=26;j++)
if(j!=x&&ch[p][j])
v[x].push_back(j),in[j]++;//大小关系,也就是直接建立边
if(tag[p])return 0;//这里有一个串,也就是第一种情况,直接不可以
p=ch[p][x];
}
return topo();
}
int main() {
IOS;
int n;cin>>n;
for(int i=1;i<=n;i++) {
string s;cin>>s;
insert(s);
v1.push_back(s);
}
//字典树处理
for(auto s:v1)
if(check(s))v2.push_back(s);
cout<<v2.size()<<'\n';
for(auto x:v2)
cout<<x<<'\n';
return 0;
}