Ӧо
APPLICATION RESEARCH OF COMPUTERS
2000Vol.17No.2P.28-30



ĸĽ㷨

ժ Ҫ ڼõĽ(LCS)㷨ʱ临ӶȷֱO(pn)O(n(m-p))mnΪȽַĳȣpӴĳȡһʱ临ӶΪO(p(m-p))ռ临ӶΪO(m+n)㷨ǰ㷨ȣp<<m£pӽmʱ㷨иٶȡ
ؼ  LCS
1 
(Longest Common SubsequenceLCS)ǽֱַɾȥַõĳַͬС磬ַabcabcabbbcacacbbΪbcacabbLCSҪַСĸһֱȽЧLCS㷨ǶNakatsuʱ临ӶΪO(n(m-p))㷨ĸĽʱ临ӶO(p(m-p))ռ临ӶΪO(m+n)
LCS㷨Ź㷺ӦáLCSоǽΪһֲѹ㷨оġ磬ڰ汾ϵͳУһļϵ޸Ĳͬİ汾²İ汾ϰ汾仯Ϊ˽ʡ洢ռ䣬ǿԽļ汾޸ĺ°汾бȽϣҳǵֺͬͲͬ֡Ͳؽԭʼļ޸ļ洢ֻ洢ļ汾Լϰ汾Ĳּͬɡʽ洢ļ汾϶ܹߴ洢Чʡļ汾ıȽϾLCS⡣LCS㷨ʱ临Ӷѹ㷨(Vdelta㷨[4])ȽԽϸߣҲѹߵĲѹ㷨Ѿ˳ⷽӦáڰ汾ϵͳУͬһļĲͬ汾бȽϲʱLCS㷨Ҫõġ
LCS㷨ڻ򹤳ȷһ²ĻǽüߵDNA뽡ߵDNAȽϣҳеͬ벻֣ͬٽзֻıȽҲLCS㷨
80ڣLCS㷨оȽ϶ࡣڣLCS㷨һЩµӦãԶоơ
ȸһЩ壺
1 (Subsequence)ַA= A[1]A[2]...A[m](A[i]AĵiĸA[i]ַƣ1<=i<m=|A||A|ʾַAĳ)ַBAָB=A[i1]A[i2]...A[ik]i1<i2<...<ikk<=m
Ҳ˵ɾȥַеַıʣַ˳͵õ˸ַһС磺becabdeaceһСӴвԭַеַ
2 (Common Subsequence)ַABCCΪABĹָCAУBС硢abdabcdbacbdĹС
3 (Longest Common SubsequenceLCS)ַABCCΪABָCABĹУҶAB⹫D|D|<=|C|
ַLCSΨһġA= cbacbaabaB=abcdbbC=bcbbD=acbbCDABС
ַAB|A|=m|B|=nm<=nLCSҪABLCS
2 Ŀǰõ㷨
Ѿ֤LCS㷨ʱ临ӶȲСO(m log n)[1]ĿǰֱȽЧ㷨Hirschberg[2]㷨ʱ临ӶȷֱΪO(pn)Լnakatsu[3]㷨ʱ临ӶΪO(n(m-p))
㷨ԼҪܵĸĽ㷨ǻ漸
4 ַA=A[1]A[2]...A[m]ַB=B[1]B[2]...B[n]A(1: i)ʾAA[1]A[2]...A[i]ͬB(1: j)ʾBB[1]B[2]...B[j]Li(k)ʾַA(1i)гΪkLCSַB(1j)jСֵùʽʾLi(k)=Minj(LCS(A(1i)B(1j))=k)
1 i[1m]Li(1)<Li(2)<Li(3)<...
2 i[1m-1](k[1m]Li+1(k) <=Li(k)
3 i[1m-1](k[1m-1]Li(k)<Li+1(k+1)
Li(k)޶
4 Li+1(k)ڣôȡֵΪ
Li+1(k)=Min(jLi(k))
jСA[i+l]=B[j]j>Li(k-1)
1234ֱ֤[2][3]4õLi(k)ĵƹʽ˵ƹϵʾΪʽͼ1

ͼ1LCAľL(p.m)
еԪL(ki)=Li(k)(1<i<=m1<k<=m)nullʾL(ki)ڡi<kʱȻL(ki)ڡ
p=Maxk(L(km)null)֤LL(pm)ڵĶԽL(1m-p+l)L(2m-p+2)L(p-1m-1) L(pm)ӦB[L(1m-p+l)]B[L(2m-p+2)]B[L(pm)]ΪABLCSpΪLCSĳȡLCSתΪLm(m⡣
һ˵ʣַABA=bcdababB=cbacbaaba(m=|a|=7n=|B|=9)ն4ĵƹʽABLͼ2

ͼ2
ABLCSΪB[1]B[3]B[5]B[6]B[8]=cababLCSĳΪ5
ӶΪO(pn)O(n(m-p))㷨ֱΪ㷨12㷨12ͨLm(mLCSģǵֻLm(mԪص˳ͬھһԪL(1i)ļ㣬ùʽL(1i)=Minj(A[i]=B[j])ԪL(ki)ö4ĵƹʽ㡣Ҫһ㷨
㷨1 ǰ˳LһԪL(11)L(12)L(1m)ڶУһֱ󵽵p+1Сֱֵp+1жΪnullΪֹڼkԪʱݶ2L(k1)>=L(k2)>=>=L(km)ԶBַӺǰɨһͿL(k1)(1<=i<=m)ɨһʱ临ӶΪO(n)㷨1ʱ临Ӷ(p+1)ΪO(pn)LĹУô洢ֻ洢ǰкһмɣռ临ӶΪO(m+n)㷨1ʺp<<m
㷨2 ǰԽ˳LһԽϵԪL(11)L(22)...ֱL(11)=null1<=mΪֹڶԽL(12)L(23)...һֱ󵽶ԽL(1s)L(2s+1)...L(tm)L(tm)<>nullΪֹʱ֤t=ps=m-p+lܹ(m-p+1)Խ߽˼㡣ڼiԽʱݶ3L(ki)<L(k+1i+1)<...ԶBַǰɨһͿL(ki)(1<=i<=m)㷨2ʱ临ӶΪO(n(m-p))ֻ洢ǰԽߺǰһԽϵԪؼɣռ临ӶΪO(m+n)㷨2ʺpmǳӽ
3 ĽĿ㷨
㷨㷨2˸ĽʹÿԽʱضBַɨһΣַʹԽÿԪصֱֵӵõΪÿԽҪ(p+1)Ԫأ(m-p+1)Խߵʱ临ӶΪO(p(m-p))ϸһΪʲôֱӵõÿԪصֵ
ַABǶַϵַƿAscii׼ַʵʼL֮ǰΪеÿַaiһбCharList[ai]а¼ַBaiֵλáַBɨתΪַбɨ衣ʵϼL(k, i)ʱɶ4ĹʽL(k+1i+1)=Min(j, L(k+l, i))j=Min1(A[i+1]=B[1]1>L(k, i))ַA[i+1]бCharList[A[i+1]]һָ¼ϴɨ赽ַA[i+1]CharList[A[i+1]]еλ1CharList[A[i+1]][l+1]jֵL(k+1, i+1)õɨַB
ڼһԽ֮ǰȽַбָĳʼֵΪеһԪءCԸ㷨ַABΪȽϵַmnֱΪַABĳȣLΪLĵǰԽߵĸԪصֵ
int lcs(char*A, char*B, int m, int n, int*L)
{
int CharList[CHAR_SET_SIZE][LIST_MAXLENGTH];//ַб
int ListLength[CHAR_SET_SIZE];//ÿбĳ
int ListIndex[CHAR_SET_SIZE];//ÿбɨλָ
int nPosA, nPosB, nPosL=0;
char ch;
//ַбַBгλðС
for (ch=a0; ch<amax;ch++)
ListLength[ch]=0;
for(nPosB=1;nPosB<=n;nPosB++)
{
ch=B[nPosB];
CharList[ch][ListLength[ch]+1]=nPosB;
ListLength[ch]++;
}
//ʼLn+1ʾnull
L[0]=0;
for(nPosL=1;nPosL<m+l;nPosL++)
L[nPosL]=n+l;
//ѭÿԽ
int nDiagonal=1;
while(true)
{
nPosL=0;
nPosA=nDiagonal;
//ָʼ
for (ch=a0; ch<amax; ch++)
ListIndex[ch]=0;
//ԽϵÿԪ
while(L[nPosL]!=n+l&&nPosA<=m)
{
nPosB=L[nPosL]+1;
ch=A[nPosA];
i=ListIndex[ch]+l;
if(i<=ListLength[ch]&&CharList[ch][i]<L[nPosL+1])
{
L[nPosL+1]=nPosB;
ListIndex[ch]++;
}
nPosL++;
nPosA++;
}
if(nPosA>m)break;
nDiagonal++;
}
return nPosL; //LCSĳ
}
4 㷨ıȽ
ͼ3Ͻܵ㷨ʱ临ӶȵʾͼͼпԿ⼸㷨Уp<<mʱpǳӽmʱ㷨3ߵЧʡڱȽļʱַΪλбȽϣѡ㷨3Ϊ㷨3ضַбȽϵģɨĵλǵַڶļıȽõġڱȽıļʱ㷨l2԰һıΪһȽϵλӶӿٶȣ㷨3ȴЧߡ

ͼ3㷨ıȽ
ѧʵ  100871
ѣ人ѧƿϵ 人 430072
ο
1Aho A.V., Hirschberg D.S., Ullman J.D.: Bounds on the Complexity of the Longest Common Subsequence Problem. J.ACM 23, 1, 112(1976)
2Hirschberg, D.S.:Algorithms for the Longest Common Subsequence Problem. J.ACM, Vol. 24, No.4, October 1977, pp.664675
3Nakatsu N., Kambayashi Y., Yajima S: A Longest Common Subsequence Algorithm Suitable for Similar Text Strings. Acta Informatica 18, 171179(1982)
4Randal C.Burns and Darrell D.E.Long: A LINEAR TIME,CONSTANT SPACE DIFFERENCING ALGORITHM
ոڣ1999716
