# HW-6
### 1
(1) 證 LCD ≦ LIS

(2) 證 LCS ≦ LIS
(3) Does it imply that there exist O(n log n) algorithms for LCD and LCS?

### 3
* [FFT](https://www.youtube.com/watch?v=h7apO7q16V0)

### 6
1. 建出所有 S 中字串的 Generalized Suffix Tree (GST)，花費時間 O(n)
2. 將 k 個字串拿去 GST 搜尋，只要該字串有出現 2 次以上的分支代表除了自己之外，也是其他字串的子字串。因為 $\sum_{i=1}^{k}m_i \le n，m_i$ 為每個字串長度，所以花費時間也是 O(n)

整體時間為 O(n)

### 7
假設字串 S 的長度為 n。
定義 max 為最長且不交集的重複子字串長度，maxIndex 為最長且不交集的重複子字串的起始位置，len 為目前搜尋過程中經過的字串長度。
1. 將給定字串建立 Suffix Tree，其中會修改節點結構，每個節點會新增 maxIndex 和 minIndex 欄位。maxIndex 為該內部節點底下的最大樹葉節點 Index，minIndex 為該內部節點底下的最小樹葉節點 Index。**在建樹過程中可先記錄 maxIndex**
2. 由 Buttom-up 的方式 (Post-order) 計算 minIndex。
Note : 不在 Step 1 就記錄的原因是子節點的 minIndex 會改變原本父節點的 minIndex。
3. 從樹根開始 DFS 搜尋整棵 Suffix Tree。若 $len \le maxIndex - minIndex$，則可以繼續往下探索；反之，該子節點底下就不用再探索了，因為會使子字串重疊到。若抵達樹葉節點，比較是否找到更長的子字串，有的話更新 max 長度以及起始位置 (maxIndex)。
4. 回傳從 maxIndex 位置開始長度為 max 的子字串，即 S[maxIndex: maxIndex + max - 1]。

Step 1 ~ 3 皆為 O(n)，故可在線性時間內完成。

### 8
觀察: **每個子字串是由某個 Suffix 的 Prefix 組成。**
字串 ababc 有 12 種不同子字串，將它建立成 Suffix Tree 如下:
只要把每條邊上的字串長度(不含結束字元$)累加起來就是所有不同子字串的數量了。因為在 Suffix Tree 中的每條從樹根到樹葉節點的路徑都代表一種 Suffix，而在此 Suffix 上我們只要列舉它的所有 Prefix 就可以了，最後把每條 Suffix 路徑上的 Prefix 列出來就是所有不同的子字串了。

1. 建立字串 T 的 Suffix Tree，時間 O(n)。
2. 累加每個節點的字串長度，想成圖來思考的話就是每邊上的字串長度(不含結束字元)，時間為 O(n)。
3. 總和即為字串 T 中有多少不同的子字串。

### 9
#### 演算法
定義 min 為在 Interval Graph 上的最小著色數
colors 為目前時間點需要至少多少顏色
1. 將活動依開始時間由小到大排序
2. 將活動依結束時間由小到大排序
3. 從最早開始的活動開始上色，直到塗完所有活動
3.1 如果目前的開始時間小於目前最早能結束的活動時間，代表這個活動和其他活動時間上有重疊到，所以要塗上新的顏色才不會撞色。若目前時間點的著色數大於 min 就更新 min。
3.2 如果目前的開始時間大於等於目前最早能結束的活動時間，代表這個活動和其他活動時間上不會衝突，所以目前使用的顏色數可以減少一色。
4. 回傳 min
#### Pseudocode
Input : 陣列 start 紀錄每個活動的開始時間、陣列 end 儲存每個活動的結束時間，共 n 個活動
Output : 在 Interval Graph 上的最小著色數

將活動依開始時間由小到大排序
將活動依結束時間由小到大排序

i = 1 // 指向 start 陣列中"正要開始"的活動
j = 0 // 指向 end 陣列中"目前最早結束"的活動
min = 1
colors = 1

while (i < n and j < n) {
    // 在 start[i] 時間點，能"最早結束"的活動 j 還在進行中
    // 代表必須為活動 i 塗上新的顏色才不會撞色 (時間衝突)
    if (start[i] < end[j]) {
        colors++
        if (colors > min) min = colors
        i++ // 活動 i 塗完色了
    } else {
        // 目前活動沒有和其他活動衝突，所以使用的顏色可以減一
        colors--
        j++; // 活動 j 結束了
    }
}

return min

#### Time O(nlgn)
主要為排序時間，while 的時間為 O(n)
#### 正確性證明
在任何時間點，最小著色數(min)一定不會小於最大衝突的數量 (K)，也就是最多有多少活動正在進行。在任意時間點，如果使用了第 K 種顏色，代表第 1 ~ K-1 個顏色都被使用了，也就是至少有 K 個活動時間同時撞到，所以至少需要 K 種顏色，而 K 是最小著色數的下界。

### 10