| 箭頭說明 | |
|---|---|
| 3 (終點) | |
| \( \nwarrow \)4 (起點) | |
| A\B | \( \varepsilon \) | a | a | c | c | b |
|---|---|---|---|---|---|---|
| \( \varepsilon \) | 0 | 0 | 0 | 0 | 0 | 0 |
| a | 0 | |||||
| b | 0 | |||||
| c | 0 | |||||
| b | 0 | |||||
| c | 0 |
| A\B | \( \varepsilon \) | a | a | c | c | b |
|---|---|---|---|---|---|---|
| \( \varepsilon \) | 0 | 0 | 0 | 0 | 0 | 0 |
| a | 0 | \( \nwarrow \)1 | \( \nwarrow \)1 | \( \leftarrow \)1 | \( \leftarrow \)1 | \( \leftarrow \)1 |
| b | 0 | \( \uparrow \)1 | \( \leftarrow \)1 | \( \leftarrow \)1 | \( \leftarrow \)1 | \( \nwarrow \)2 |
| c | 0 | \( \uparrow \)1 | \( \leftarrow \)1 | \( \nwarrow \)2 | \( \nwarrow \)2 | \( \leftarrow \)2 |
| b | 0 | \( \uparrow \)1 | \( \leftarrow \)1 | \( \uparrow \)2 | \( \leftarrow \)2 | \( \nwarrow \)3 |
| c | 0 | \( \uparrow \)1 | \( \leftarrow \)1 | \( \nwarrow \)2 | \( \nwarrow \)3 | \( \leftarrow \)3 |
上方按鈕操作表格。
(A拿自己第一個a和B拿自己第一個a比對)
看第一個row的a對上第一個column的a，有match到，所以左上角那格數值+1(左上角那個為0)=0+1=1, 箭頭往左上。
(A拿自己第一個a和B拿自己aa比對)
看第一個row的a對上第二個column的a，有match到，所以左上角那格數值+1(有match到是基於第二個column的a，這跟第一個column的a沒有關係喔!), 箭頭往左上。
(A拿自己第一個a和B拿自己aac比對)
第一個row的a對上第三個column的c，沒有match到，所以看上面左邊的數值哪個較大就選它，箭頭也選那邊，這裡選左邊那個。
注意!! 如果上面左邊數值一樣，都可以選，不會影響最長長度，只會影響最後序列內容是什麼排列，這也就意味著序列不唯一。
(A拿自己第一個a和B拿自己aacc比對)
第一個row的a對上第四個column的c，沒有match到，上面左邊選較大的值，箭頭向左。
(A拿自己第一個a和B拿自己aaccb比對)
第一個row的a對上第五個column的b，沒有match到，上面左邊選較大的值，箭頭向左。
(A拿自己ab和B拿自己a比對)
第二個row的b對上第一個column的a，沒有match到，上面左邊選較大的值，箭頭向上。
(A拿自己ab和B拿自己aa比對)
注意! 這裡有一樣的值做選擇，箭頭方向會影響序列排列，並不會影響最長的結果。
第二個row的b對上第二個column的a，沒有match到，上面左邊選較大的值，數值都一樣大，都可以選，這裡箭頭選向左。
(A拿自己ab和B拿自己aac比對)
注意! 這裡有一樣的值做選擇，箭頭方向會影響序列排列，並不會影響最長的結果。
第二個row的b對上第三個column的c，沒有match到，上面左邊選較大的值，數值都一樣大，都可以選，這裡箭頭選向左。
(A拿自己ab和B拿自己aacc比對)
注意! 這裡有一樣的值做選擇，箭頭方向會影響序列排列，並不會影響最長的結果。
第二個row的b對上第四個column的c，沒有match到，上面左邊選較大的值，數值都一樣大，都可以選，這裡箭頭選向左。
(A拿自己ab和B拿自己aaccb比對)
第二個row的b對上第五個column的b，有match到, 左上那格+1=2,箭頭向左上。
(A拿自己abc和B拿自己a比對)
第三個row的c對上第一個column的a，沒有match到，上面左邊選較大的值，箭頭向上。
(A拿自己abc和B拿自己aa比對)
注意! 這裡有一樣的值做選擇，箭頭方向會影響序列排列，並不會影響最長的結果。
第三個row的c對上第二個column的a，沒有match到，上面左邊選較大的值，箭頭向左。
(A拿自己abc和B拿自己aac比對)
第三個row的c對上第三個column的c，有match到, 左上那格+1=2,箭頭向左上。
(A拿自己abc和B拿自己aacc比對)
第三個row的c對上第四個column的c，有match到, 左上那格+1=2(這是基於ab和aa有1個長度的共同子序列基礎下，再加上B現在這個c和A現在這個c有match到才+1的),箭頭向左上。
(A拿自己abc和B拿自己aaccb比對)
注意! 這裡有一樣的值做選擇，箭頭方向會影響序列排列，並不會影響最長的結果。
第三個row的c對上第五個column的b，沒有match到，上面左邊選較大的值，數值都一樣大，都可以選，這裡箭頭選向左。
(A拿自己abcb和B拿自己a比對)
第四個row的b對上第一個column的a，沒有match到，上面左邊選較大的值，箭頭向上。
(A拿自己abcb和B拿自己aa比對)
注意! 這裡有一樣的值做選擇，箭頭方向會影響序列排列，並不會影響最長的結果。
第四個row的b對上第二個column的a，沒有match到，上面左邊選較大的值，箭頭向左。
(A拿自己abcb和B拿自己aac比對)
注意! 這裡有一樣的值做選擇，箭頭方向會影響序列排列，並不會影響最長的結果。
第四個row的b對上第三個column的c，沒有match到，上面左邊選較大的值，箭頭向上。
(A拿自己abcb和B拿自己aacc比對)
注意! 這裡有一樣的值做選擇，箭頭方向會影響序列排列，並不會影響最長的結果。
第四個row的b對上第四個column的c，沒有match到，上面左邊選較大的值，箭頭向左。
(A拿自己abcb和B拿自己aaccb比對)
第四個row的b對上第五個column的b，有match到, 左上那格+1=3,箭頭向左上。
(A拿自己abcbc和B拿自己a比對)
第五個row的c對上第一個column的a，沒有match到，上面左邊選較大的值，箭頭向上。
(A拿自己abcbc和B拿自己aa比對)
注意! 這裡有一樣的值做選擇，箭頭方向會影響序列排列，並不會影響最長的結果。
第五個row的c對上第二個column的a，沒有match到，上面左邊選較大的值，箭頭向左。
(A拿自己abcbc和B拿自己aac比對)
第三個row的c對上第三個column的c，有match到, 左上那格+1=2,箭頭向左上。
(A拿自己abcbc和B拿自己aacc比對)
第五個row的c對上第四個column的c，有match到, 左上那格+1=3(這是基於abcb和aacc有2個長度的共同子序列基礎下，再加上B現在這個c和A現在這個c有match到才+1的),箭頭向左上。
(A拿自己abcbc和B拿自己aaccb比對)
注意! 這裡有一樣的值做選擇，箭頭方向會影響序列排列，並不會影響最長的結果。
第五個row的c對上第五個column的b，沒有match到，上面左邊選較大的值，數值都一樣大，都可以選，這裡箭頭選向左。
回推最佳解內容
找到最右下角最大數值為3，也就是最長共同子序列長度為3。
要找到序列，就從最右下開始回推，以陣列index的形式來說明，排除預設的0，這裡是\( 5\times 5 \)的矩陣，A字串為1到5，B字串也為1到5，舉例表格最右下角編號為[5][5]。
開始回推，[5][5]箭頭向左，到[5][4]箭頭向左上，這格標記起來，因為他們有共同的元素，接著順著箭頭到[4][3],箭頭向上，到[3][3]，箭頭左上，標記，到[2][2]箭頭向左，到[2][1]，箭頭向上，[1][1]箭頭向左上，標記，最後可得最長共同子序列長度為3，內容為acc(當然箭頭選擇上面左邊的不一樣，內容也會不一樣，這LCS內容可能為acb)。