luogu P3065 first——trie树相关

题目描述

Bessie has been playing with strings again. She found that by

changing the order of the alphabet she could make some strings come before all the others lexicographically (dictionary ordering).

For instance Bessie found that for the strings "omm", "moo", "mom", and "ommnom" she could make "mom" appear first using the standard alphabet and that she could make "omm" appear first using the alphabet

"abcdefghijklonmpqrstuvwxyz". However, Bessie couldn't figure out any way to make "moo" or "ommnom" appear first.

Help Bessie by computing which strings in the input could be

lexicographically first by rearranging the order of the alphabet. To compute if string X is lexicographically before string Y find the index of the first character in which they differ, j. If no such index exists then X is lexicographically before Y if X is shorter than Y. Otherwise X is lexicographically before Y if X[j] occurs earlier in the alphabet than Y[j].

给出n个字符串，问哪些串能在特定的字母顺序中字典序最小。

　　　　-by luogu

http://daniu.luogu.org/problem/show?pid=3065

字典(trie)树，没什么好讲的；

建字典树后，如何check单词?

首先性质1：

　　一个单词的前缀是单词的单词非法；

--显然，无论如何规定字典序，空就是最高的；

然后在字典树上i位置选j字母——意味着我们认为j字母比i的其他子节点小，假设k字母正是这样一个子节点；

这样的话，继续走下去时，如果在某个节点时，我们想走k字母但是发现j字母也是这个节点的儿子，那我们就走不了k了；

然后这个单词非法；

可以考虑用拓扑排序的思想规定大小;

（如果可以走j,则其它子节点字母向j连有向边构成图，然后check就是从一个节点dfs,若遍历到一个点，他也是当前父节点的一个儿子，则单词非法，先check再建边）；

我一开始觉得这个方法效率玄学；

然而其实图中无环所以dfs是单次O(26)的，于是，总效率是O(num*26)的（num总字符数）

十分合适;

代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 struct Trie{
 6     int ch[26];
 7     int flag,size;
 8 };
 9 Trie trie[300010];
10 int n,tot;
11 string word[300010];
12 string word2[300010];
13 int ans;
14 int e[26][26];
15 void Init();
16 void bui_trie();
17 void check(int );
18 int dfs(int ,int );
19 int main()
20 {
21     int i,j,k;
22     Init();
23     scanf("%d",&n);
24     bui_trie();
25     for(i=1;i<=n;i++){
26         memset(e,0,sizeof(e));
27         check(i);
28     }
29     printf("%d
",ans);
30     for(i=1;i<=ans;i++)
31         cout<<word2[i]<<'
';
32 }
33 void Init(){
34     memset(trie,0,sizeof(trie));
35     n=tot=ans=0;
36 }
37 void bui_trie(){
38     int i,j,k;
39     for(i=1;i<=n;i++){
40         cin>>word[i];k=0;
41         for(j=0;j<word[i].size();j++){
42             if(!trie[k].ch[word[i][j]-'a'])
43                 trie[k].ch[word[i][j]-'a']=++tot;
44             k=trie[k].ch[word[i][j]-'a'];
45         }
46         trie[k].flag=1;
47     }
48 }
49 void check(int x){
50     int i,j,k=0,l;
51     for(i=0;i<word[x].size();i++){
52         if(trie[k].flag)return;
53         j=trie[k].ch[word[x][i]-'a'];
54         if(dfs(word[x][i]-'a',k))
55             return;
56         for(l=0;l<=25;l++)
57             if(trie[k].ch[l]&&l!=word[x][i]-'a')
58                 e[l][++e[l][0]]=word[x][i]-'a';
59         k=j;
60     }
61     word2[++ans]=word[x];
62 }
63 int dfs(int now,int k){
64     int re=0,i;
65     for(i=1;i<=e[now][0];i++)
66         if(!trie[k].ch[e[now][i]]&&!re)
67             re=dfs(e[now][i],k);
68         else
69             return 1;
70         return re;
71 }