Homework 11-8
=
###### tags: `Course - Algorithmics`
## Design
偷懶一下，把LCS當成LIS來解，這邊複製貼上一下程式作業4的內容：
1. 用Hunt–Szymanski algorithm把兩個字串合成成一串數字。
e.g.
首先把兩個字串看成一個2維坐標系，在字元相同的座標打上星號並記錄下來。
然後對這些座標做Counting Sort
2. 接下來就是畫圖，因為我們要找LIS，所以只能由小的頂點接到大的頂點，詳細規則如下：
1. 每個數字都是一個頂點。
2. 若以下條件成立，則頂點A有一條連到B的邊 (A→B)：
* 原序列中，B在A的右邊。
* B的值比A大 (B.value > A.value)。
3. 需要一個額外的頂點當作終點 (end)。
4. 每個頂點都有一條連到終點的邊 (e.g. A→end)。
上面舉的例子畫成圖長這樣：
3. 這張圖是一張DAG，既然要找最長序列，那畫成圖後就是最長路徑(每條邊的權重都是1)，可以看出上圖其中一條最長路徑是1→3→5→end (看不出來的話是因為我畫的太醜)。
4. 上課時有說，要找DAG的最長路徑，只要把邊的權重改成負的(或是把小於改大於)，然後找最短路徑就好。因為只有一個起點的最短路徑比較好算，所以把邊反向，然後把end當成起點。
5. 用LIS回推LCS。
## Pseudo Code
### 步驟1

# R為字元編碼的範圍
p[R] = Null # 為了進一步縮短時間，所以不使用Counting Sort，直接random access
d[] # list
adj[] # dictionary

input s1[], s2[]
if s1.length > s2.length: swap(s1, s2)
# 因為2nd components是遞減的，所以倒過來看
for i from s1.length to 1:
    p[decode(s1[i])].append(i)

# s為合併後的數列
for c in s2:
    if p[decode(c)] == Null: continue
    for i in p[decode(c)]:
        s.append(i)
        
# 建立DAG，應該有更快的方法，但我不知道
for i from 1 to s.length:
    adj.append(s[i])
    adj[s[i]].append(end)
    for j from i + 1 to s.length:
        if s[j] > s[i]:
            adj[s[i]].append(s[j])
s.append(end)

# 反向
adj_T[]
    for l in adj:
        for v in l:
            adj_T[v].append(l.begin)
    adj = adj_T
    

### 步驟2 Type I

v = s.length
π[v] = Null, d[v] = -∞ # create list
d[end] = 0
for u in s.reverse:
    for v in adj[u]:
        if d[v] < d[u] + 1:
            d[v] = d[u] + 1
            π[v] = u
            
result[] # LIS
v = argmax(d)
while(v != end):
    result.append(v)
    v = π[v]

### 步驟2 Type II ??? (應該不是這樣，我只是反過來做而已)

v = s.length
π[v] = Null, d[v] = 0 # create list
for u in s:
    for v in adj[u]:
        if d[u] < d[v] + 1:
            d[u] = d[v] + 1
            π[u] = v
            
result[] # LIS
v = π[end]
while(v != Null):
    result.append(v)
    v = π[v]
result = result.reverse

### 步驟3

# 用LIS回推LCS
for i in result:
    print s1[i]

## Analysis
* 假設s1的長度為m，s2的長度為n，且m ≤ n。
* 時間複雜度：
跟建adjacency list的時間有關，我用的方法是$\Theta(m^2)，應該還能再更快$