[字典樹]OI練習題：詞鏈 link 解題報告

Title: 詞鏈【傳送門】

Input: link.in

Output: link.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

【問題描述】
給定一個僅包含小寫字母的英文單詞表，其中每個單詞最多包含 50 個字母。

如果一張由一個詞或多個片語成的表中，每個單詞（除了最後一個）都是排在它後面的單詞的前綴，則稱此表為一個詞鏈。例如下面的單片語成了一個詞鏈：

i

int

integer

而下面的單詞不組成詞鏈：

integer

intern

請在給定的單詞表中取出一些詞，組成最長的詞鏈。最長的詞鏈就是包含單詞數最多的詞鏈。

資料保證給定的單詞表中，單詞互不相同，並且單詞按字典順序排列。

【輸入格式】

第一行一個整數 n ，表示單詞表中單詞數。

下接 n 行每行一個單詞。

【輸出格式】

一個整數，表示最長詞鏈長度。

【輸入輸出樣例】

輸入:

link.in

5

i

int

integer

intern

internet

輸出:

link.out

4

【資料範圍】

50% 的資料， n<=1000

100% 的資料， n<=10000

【分析】

看到這題，我立刻想到了兩種解法，一個是DP，一個是Trie。

解法一： 動態規劃

和最长XX序列一样，F[i]表示以第i个字符串结尾的最长词链的长度。

邊界條件：

               F[1]=1

狀態轉移方程：

                   F[i]=Max{F[j]}+1 (1<=j<=i-1)  (str[j]是str[i]的前缀)

目标状态：

                   Max{F[i]} (1<=i<=N)

時間複雜度： O(L*N^2) (說明：L為字符串的平均長度，下同)

期望得分：50分

====我的代碼（50分）====

裸代碼RawCode

C++语言: Codee#25392

01 /*
02 *Problem: 詞鏈 Link
03 *Author: Yee-fan Zhu
04 *Website: http://blog.yeefanblog.tk/
05 *Method: Dynamic Programming（50分）
06 */
07 #include <cstdio>
08 #include <cstring>
09 #include <cstdlib>
10 using namespace std;
11
12 const int MAXN=10001;
13 int N;
14 char word[MAXN][51];
15 int F[MAXN];
16 int Ans=1;
17
18 int MAX(int a,int b)
19 {
20     return a>b?a:b;
21 }
22
23 void init()
24 {
25     scanf("%d\n",&N);
26     for (int i=1;i<=N;i++)
27         scanf("%s\n",&word[i]);
28     F[0]=0,F[1]=1;
29 }
30
31 void dynamic()
32 {
33     for (int i=2;i<=N;i++)
34     {
35         int Max=0;
36         for (int j=1;j<=i-1;j++)
37         {
38             bool flag=true;
39             for (unsigned int k=0;k<strlen(word[j]);k++)
40             {
41                 if(word[j][k]!=word[i][k])
42                 {
43                     flag=false;
44                     break;
45                 }
46             }
47             if(flag && F[j]>Max)
48                 Max=F[j];
49         }
50         F[i]=Max+1;
51         if(F[i]>Ans)
52             Ans=F[i];
53     }
54     printf("%d\n",Ans);
55 }
56
57 int main()
58 {
59     freopen("link.in","r",stdin);
60     freopen("link.out","w",stdout);
61     init();
62     dynamic();
63     return 0;
64 }

解法二： 字典樹Trie

构造一个Trie树，从叶子节点向上统计被标记的节点数即可。

時間複雜度：O(K*N)
期望得分： 100分
=====CODE=====

裸代碼RawCode

C++语言: Codee#25393

01 /*
02 *Problem: 詞鏈 Link
03 *Author: Yee-fan Zhu
04 *Website: http://blog.yeefanblog.tk/
05 *Method: Trie Tree
06 */
07 #include <cstdio>
08 #include <cstring>
09 #include <cstdlib>
10 using namespace std;
11
12 int N;
13 int Ans=1;
14 const int SonNum=30;
15 const int base='a';
16
17 class Trie
18 {
19 public:
20     bool isStr;
21     int Link;
22     class Trie *Son[SonNum];
23 };
24 Trie *Root;
25
26 Trie *NewTrie()
27 {
28     Trie *temp=new Trie;
29     temp->isStr=false;
30     temp->Link=0;
31     for(int i=0;i<SonNum;i++)
32         temp->Son[i]=NULL;
33     return temp;   
34 }
35
36 void Insert(Trie *pnt,char *s,int len)
37 {
38     Trie *temp=pnt;
39     int Link=0;
40     for (int i=0;i<len;i++)
41     {
42         if(temp->isStr)
43             Link=temp->Link;
44         if(temp->Son[s[i]-base]==NULL)
45         {
46             temp->Son[s[i]-base]=NewTrie();
47             temp->Link=Link;
48         }
49         temp=temp->Son[s[i]-base];
50     }
51     temp->isStr=true;
52     temp->Link=Link+1;
53     if(temp->Link>Ans)
54         Ans=temp->Link;
55 }
56
57 int MAX(int a,int b)
58 {
59     return a>b?a:b;
60 }
61
62 void init()
63 {
64     scanf("%d\n",&N);
65     char str[51];
66    
67     Root=NewTrie();
68     Root->isStr=true;
69     Root->Link=0;
70    
71     for (int i=1;i<=N;i++)
72     {
73         memset(str,'\0',sizeof(str));
74         scanf("%s\n",&str);
75         Insert(Root,str,strlen(str));
76     }
77     printf("%d\n",Ans);
78 }
79
80
81 int main()
82 {
83     freopen("link.in","r",stdin);
84     freopen("link.out","w",stdout);
85     init();
86     return 0;
87 }