bzoj 3012 First!

Posted on | Views:

$Trie$ 树 + 拓扑排序判环.

将所有串插入到一棵 $Trie$ 树中.

若一个字符串 $s_i$ 成为了字典序最小的串,因为这些串互不相同,所以必须要求其他串都不能是 $s_i$ 的前缀.

即在 $Trie$ 树上,根节点到这个串的终止节点路径上不能有其它的串的终止节点.

另一个条件是根到这个节点路径上每条边字符的字典序比它父亲向所有兄弟的边字符的字典序小.

这可以用若干条有向边表示字符间的大小关系,建出图后拓扑排序,若有环,则不合法,否则合法.

时间复杂度 $O(|S|^2\cdot n+|S|\cdot \sum |s|)$ ,其中 $S$ 代表字符集, $s$ 代表读入的串.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=3e5+10,N=3e4+10,S=26;
char buf[N],s[MAXN];
int n,len;
int G[S][S],deg[N],ans[N],ans_cnt=0;
int d[N],cnt,vis[N];
void del(int u)
{
	++cnt;
	vis[u]=1;
	for(int v=0;v<S;++v)
		if(G[u][v])
		{
			d[v]-=G[u][v];
			if(!d[v])
				del(v);
		}
}
bool topsort()
{
	memset(vis,0,sizeof vis);
	memcpy(d,deg,sizeof d);
	cnt=0;
	for(int i=0;i<S;++i)
		if(!d[i] && !vis[i])
			del(i);
	return cnt==S;
}
struct Trie
{
	int ch[MAXN][S],idx;
	int val[MAXN];
	Trie(){idx=0;}
	void ins(int id)
	{
		int u=0;
		for(int i=1;i<=len;++i)
		{
			int c=buf[i]-'a';
			if(!ch[u][c])
				ch[u][c]=++idx;
			u=ch[u][c];
		}
		val[u]=id;
	}
	void dfs(int u)
	{
		if(val[u])
		{
			if(topsort())
			{
				ans[val[u]]=1;
				++ans_cnt;
			}	
			return;
		}
		int q[S],t=0;
		for(int c=0;c<S;++c)
		{
			int v=ch[u][c];
			if(!v)
				continue;
			q[++t]=c;
		}
		for(int c=0;c<S;++c)
		{
			int v=ch[u][c];
			if(!v)
				continue;
			for(int i=1;i<=t;++i)
				if(q[i]!=c)
				{
					++G[c][q[i]];
					++deg[q[i]];
				}	
			dfs(v);
			for(int i=1;i<=t;++i)
				if(q[i]!=c)
				{
					--G[c][q[i]];
					--deg[q[i]];
				}	
		}
	}
}T;
int lp[N],rp[N];
int main()
{
	n=read();
	int tot=0;
	for(int i=1;i<=n;++i)
	{
		scanf("%s",buf+1);
		len=strlen(buf+1);
		lp[i]=tot+1;
		for(int j=1;j<=len;++j)
			s[++tot]=buf[j];
		rp[i]=tot;
		T.ins(i);
	}
	T.dfs(0);
	printf("%d\n",ans_cnt);
	for(int i=1;i<=n;++i)
		if(ans[i])
		{
			for(int j=lp[i];j<=rp[i];++j)
				putchar(s[j]);
			puts("");
		}
	return 0;
}