經典演算法題每日演練——第四題最長公共子序列

一：作用
最長公共子序列的問題常用於解決字串的相似度，是一個非常實用的演算法，作為碼農，此演算法是我們的必備基本功。
二：概念
舉個例子，cnblogs 這個字串中子序列有多少個呢？很顯然有 27 個，比如其中的 cb,cgs 等等都是其子序列，我們可以看出
子序列不見得一定是連續的，連續的那是子串。
我想大家已經瞭解了子序列的概念，那現在可以延伸到兩個字串了，那麼大家能夠看出：cnblogs 和 belong 的公共子序列嗎？
在你找出的公共子序列中，你能找出最長的公共子序列嗎？

從圖中我們看到了最長公共子序列為 blog，仔細想想我們可以發現其實最長公共子序列的個數不是唯一的，可能會有兩個以上，
但是長度一定是唯一的，比如這裏的最長公共子序列的長度為 4 。

三：站羣解決方案
<1> 列舉法
這種方法是最簡單，也是最容易想到的，當然時間複雜度也是龜速的，我們可以分析一下，剛才也説過了 cnblogs 的子序列
個數有 27 個，延伸一下：一個長度為 N 的字串，其子序列有 2N 個，每個子序列要在第二個長度為 N 的字串中去匹配，匹配一次
需要 O(N) 的時間，總共也就是 O(N*2N)，可以看出，時間複雜度為指數級，恐怖的令人窒息。

<2> 動態規劃
既然是經典的題目肯定是有優化空間的，並且解題方式是有固定流程的，這裏我們採用的是矩陣實現，也就是二維陣列。
第一步：先計算最長公共子序列的長度。
第二步：根據長度，然後通過回溯求出最長公共子序列。
現有兩個序列 X={x1,x2,x3，…xi}，Y={y1,y2,y3，….，yi}，
設一個 C[i,j]: 儲存 Xi 與 Yj 的 LCS 的長度。
遞推方程為：

不知道大家看懂了沒？動態規劃的一個重要性質特點就是解決 “子問題重疊” 的場景，可以有效的避免重複計算，根據上面的
公式其實可以發現 C[i,j] 一直儲存著當前 (Xi,Yi) 的最大子序列長度。

1 using System;
2 namespace ConsoleApplication2
3 {
4 public class Program
5 {
6 static int[,] martix;
7
8 static string str1 = “cnblogs”;
9 static string str2 = “belong”;
10
11 static void Main(string[] args)
12 {
13 martix = new int[str1.Length + 1, str2.Length + 1];
14
15 LCS(str1, str2);
16
17 //只要拿出矩陣最後一個位置的數字即可
18 Console.WriteLine(“ 當前最大公共子序列的長度為:{0}”, martix[str1.Length, str2.Length]);
19
20 Console.Read();
21 }
22
23 static void LCS(string str1, string str2)
24 {
25 //初始化邊界，過濾掉 0 的情況
26 for (int i = 0; i <= str1.Length; i++) 27 martix[i, 0] = 0; 28 29 for (int j = 0; j <= str2.Length; j++) 30 martix[0, j] = 0; 31 32 //填充矩陣 33 for (int i = 1; i <= str1.Length; i++) 34 { 35 for (int j = 1; j <= str2.Length; j++) 36 { 37 //相等的情況 38 if (str1[i - 1] == str2[j - 1]) 39 { 40 martix[i, j] = martix[i - 1, j - 1] + 1; 41 } 42 else 43 { 44 //比較“左邊”和“上邊“，根據其max來填充 45 if (martix[i - 1, j] >= martix[i, j – 1])
46 martix[i, j] = martix[i – 1, j];
47 else
48 martix[i, j] = martix[i, j – 1];
49 }
50 }
51 }
52 }
53 }
54 }

圖大家可以自己畫一畫，程式碼完全是根據上面的公式照搬過來的，長度的問題我們已經解決了，這次要解決輸出最長子序列的問題，
我們採用一個標記函式 Flag[i,j]，當
①：C[i,j]=C[i-1,j-1]+1 時標記 Flag[i,j]=”left_up”; （左上方箭頭）
②：C[i-1,j]>=C[i,j-1] 時標記 Flag[i,j]=”left”; （左箭頭）
③: C[i-1,j]= martix[i, j – 1])
53 {
54 martix[i, j] = martix[i – 1, j];
55 flag[i, j] = “left”;
56 }
57 else
58 {
59 martix[i, j] = martix[i, j – 1];
60 flag[i, j] = “up”;
61 }
62 }
63 }
64 }
65 }
66
67 static void SubSequence(int i, int j)
68 {
69 if (i == 0 || j == 0)
70 return;
71
72 if (flag[i, j] == “left_up”)
73 {
74 Console.WriteLine(“{0}: 當前座標:（{1},{2}）”, str2[j – 1], i – 1, j – 1);
75
76 //左前方
77 SubSequence(i – 1, j – 1);
78 }
79 else
80 {
81 if (flag[i, j] == “up”)
82 {
83 SubSequence(i, j – 1);
84 }
85 else
86 {
87 SubSequence(i – 1, j);
88 }
89 }
90 }
91 }
92 }

由於直接繪圖很麻煩，嘿嘿，我就用手機拍了張：

好，我們再輸入兩個字串：

1 static string str1 = “abcbdab”;
2
3 static string str2 = “bdcaba”;

通過上面的兩張圖，我們來分析下它的時間複雜度和空間複雜度。
時間複雜度：構建矩陣我們花費了 O(MN) 的時間，回溯時我們花費了 O（M+N) 的時間，兩者相加最終我們花費了 O(MN) 的時間。
空間複雜度：構建矩陣我們花費了 O(MN) 的空間，標記函式也花費了 O(MN) 的空間，兩者相加最終我們花費了 O(MN) 的空間。

一：作用
最長公共子序列的問題常用於解決字串的相似度，是一個非常實用的演算法，作為碼農，此演算法是我們的必備基本功。
二：概念
舉個例子，cnblogs 這個字串中子序列有多少個呢？很顯然有 27 個，比如其中的 cb,cgs 等等都是其子序列，我們可以看出
子序列不見得一定是連續的，連續的那是子串。
我想大家已經瞭解了子序列的概念，那現在可以延伸到兩個字串了，那麼大家能夠看出：cnblogs 和 belong 的公共子序列嗎？
在你找出的公共子序列中，你能找出最長的公共子序列嗎？