作者Rey (醒悟)
看板CS_Softball
標題Re: LCS
時間Sun May 19 17:42:39 2002
※ 引述《garytsai (睡吧~~)》之銘言：
: 現在要求X,Y的LCS
LCS指的是longest common substring還是subsequence?
我想你指的應該是後者
介紹你們一個DP (Dynamic Programming)的方法
對兩個string A: 1aa23a4a5a |A|=10
B: b1bb2b3b |B|=8
如果兩個character match得一分, 否則得零分
建一個矩陣 M, size為|B|*|A|
1 a a 2 3 a 4 a 5 a
b 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1
b 1 1 1 1 1 1 1 1 1 1
b 1 1 1 1 1 1 1 1 1 1
2 1 1 1 2 2 2 2 2 2 2
b 1 1 1 2 2 2 2 2 2 2
3 1 1 1 2 3 3 3 3 3 3
b 1 1 1 2 3 3 3 3 3 3
M[x][y]=max{ M[x-1][y], M[x][y-1], M[x-1][y-1] }+( 0 if A[x]!=B[y],
1 if A[x]==B[y])
填完這個矩陣的time complexity為 O(|A|*|B|)
最右下角的數字就是LCS的長度, 要如何知道LCS是哪幾個char位於哪裡呢?
很簡單, 稍微觀察一下那個矩陣就會發現
分數發生變化的地方就是LCS的某個字元所在
由右下角往左上角找, (先上再左或先左再上都可以啦)
time complexity為 O(|A|+|B|)
total time complexity=O(|A|*|B|+|A|+|B| )=O(|A|*|B|)
※ 編輯: Rey 來自: 140.112.231.73 (05/19 17:47)
※ 編輯: Rey 來自: 140.112.30.18 (05/19 18:00)