字典树0pts求助
查看原帖
字典树0pts求助
526017
COsm0s楼主2023/4/29 17:57

RT.

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N = 3e5 + 5, mod = 1e9 + 7;
inline int read() {
	int x = 0, m = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') m = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	return x * m;
}
inline void write(int x) {
	if(x < 0) {
		putchar('-');
		write(-x);
		return;
	}
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
string s[N];
int trie[N][50], tag[N], in[50], g[50][50], cnt;
string ans[N];
int tot;
inline int G(char x) {
	return x - 96;
}
inline void insert(string s) {
	int len = s.size(), p = 1;
	s = " " + s;
	for(int i = 1; i <= len; i ++) {
		if(!trie[p][G(s[i])]) trie[p][G(s[i])] = ++ tot;
		p = trie[p][G(s[i])];
	}
	tag[p] ++;
}
inline bool slove(string s) {
	int u = 1, len = s.size();
	s = " " + s;
	memset(in, 0, sizeof in);
	memset(g, 0, sizeof g);
	for(int i = 1; i <= len; i ++) {
		if(tag[u]) return 0;
		int v = s[i] - 96;
		for(int j = 1;  j <= 26; j ++) {
			if(v != j && trie[u][j] && !g[v][j]) g[v][j] = 1, in[j] ++;
		}
		u = trie[u][v];
	}
	queue<int> q;
	for(int i = 1; i <= 26; i ++) if(!in[i]) q.push(i);
	while(!q.empty()) {
		int now = q.front();
		q.pop();
		for(int i = 1; i <= 26; i ++) {
			if(g[now][i]) {
				in[i] --;
				if(!in[i]) q.push(i);
			}
		}
	}
	for(int i = 1; i <= 26; i ++) if(in[i]) return 0;
	return 1;
}
signed main() {
	int n = read();
	for(int i = 1; i <= n; i ++) cin >> s[i], insert(s[i]);
	for(int i = 1; i <= n; i ++) {
		bool flag = slove(s[i]);
		if(flag) ans[++ cnt] = s[i];
	}
	cout << cnt << endl;
	for(int i = 1; i <= cnt; i ++) cout << ans[i], putchar('\n');
	return 0;
}
2023/4/29 17:57
加载中...