作者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)