LCS是什么

LCS是Longest Common Subsequence的縮寫，即最長公共子序列。它與子串的區(qū)別是子串要連續(xù)，子序列不連續(xù)。

LCS可以用來做什么

1，生物學(xué)上用來進(jìn)行基因序列比對，以推測序列的結(jié)構(gòu)、功能和演化過程

2，用來描述兩段文字的”相似性“，可以用來辨別是不是抄襲

怎么計(jì)算LCS

1，暴力窮舉法

就是把兩個(gè)序列所有的子序列都列出來，然后一一進(jìn)行比較。

例如一個(gè)子序列有n個(gè)字符，每個(gè)字符按順序放桌子上，動(dòng)一下一個(gè)字符就會產(chǎn)生一個(gè)子序列，對于每個(gè)字符，存在拿走和不拿走兩種情況，所以，一共有2的n次方個(gè)子序列，再和別個(gè)子序列比較，瘋了。

2，動(dòng)態(tài)規(guī)劃法。

假如有字符串A和B,?An表示A前n個(gè)字符組成的子串，Bm表示B前m個(gè)字符組成的子串。如果An=Bm，則LCS(An,Bm)=LCS(An-1,Bm-1)+An，這種計(jì)算方法一樣，規(guī)模變小的方法一般叫動(dòng)態(tài)規(guī)劃。如果最后一個(gè)不一樣，就砍掉A的最后一個(gè)和B比，或者砍掉B的最后一個(gè)和A比，取最大的，公式如下：

這么抽象，看看可視化二維數(shù)組吧

def lcs(a, b):# 參數(shù)是兩個(gè)字符串a(chǎn),b lena = len(a) lenb = len(b) # 用于存儲Aj和Bi的最長公共子序列長度 opt = [[0 for i in range(lena + 1)] for j in range(lenb + 1)] # 用于存儲轉(zhuǎn)換規(guī)則，如果是跳轉(zhuǎn)，即有字母一樣了，存1，如果是上邊的大于左邊的存-1，否則保持0不變 flag = [[0 for i in range(lena + 1)] for j in range(lenb + 1)]