在參閱《A Longest Common Subsequence Algorithm Suitable for Similar Text Strings》（Narao Nakatsu，Yahiko Kambayashi，Shuzo Yajima著）後。發現該算法可以利用線性空間求出最長公共子序列。該算法的時間占用O（n（m-p+1）），p為最長公共子序列的長度。
字符串A和字符串B，計算LCS(A,B)
定義一：設M=Len(A)，N=Len(B)，不妨設M≤N。
定義二：A=a1a2……aM，表示A是由a1a2……aM這M個字符組成
B=b1b2……bN，表示B是由b1b2……bN這N個字符組成
LCS(i,j)=LCS(a1a2……ai,b1b2……bj)，其中1≤i≤M，1≤j≤N
定義三：L(k,i)表示，所有與字符串a1a2……ai有長度為k的LCS的字符串b1b2……bj中j的最小值。
用公式表示就是：L(k,i)=Min｛j｝ Where LCS(i,j)=k
用一個例子來說明：A="CD"，B="CEFDRT"。
很明顯的是LCS(2,1)=1，LCS(2,2)=1，LCS(2,3)=1。
滿足LCS(2,j)=1這個條件的j有三個，分別是j=1、j=2、j=3。其中j最小值是1。故L(1,2)=1
為了推導L的計算，有下面幾個定理。
定理一：任意的i，1≤i≤M。有L(1,i)＜L(2,i)＜L(3,i)……
定理二：任意的i，1≤i≤M-1。任意的k，1≤k≤M。有L(k,i+1)≤L(k,i)
定理三：任意的i，1≤i≤M-1。任意的k，1≤k≤M－1。有L(k,i)＜L(k+1,i+1)
定理四：如果L(k,i+1)存在，則L(k,i+1)的計算公式為
L(k,i+1)=Min｛Min｛j｝，L(k,i)｝ Where ｛ai+1=bj And j>L(k-1,i)｝
上面四個定理證明從略。可以從上面四個定理推導出L的計算。
故，L的計算公式為
①L(1,1)=Min｛j｝ Where ｛a1=bj｝
②L(1,i)=Min｛Min｛j｝ Where ｛ai=bj｝，L(1,i-1)｝ 此時，1<i≤M
③L(k,i)=Min｛Min｛j｝ Where ｛ai=bj And j＞L(k-1,i-1)｝，L(k,i-1)｝ 此時，1<i≤M，1<k≤M
注：以上公式中，若找不到滿足Where後面條件的j，則j=MaxValue
當i＜k時，則L(k,i)=MaxValue
MaxValue是一個常量，表示“不存在”
在實際的算法實現中，為了簡化運算，再次提出幾個定義。
定義： L(0,i)=0 1≤i≤M
L(k,0)=MaxValue 1<k≤M
MaxValue=N+1 （只要定義一個j不可能取到的值就可以了）
則，在①中的公式可以寫成
L(1,1)=Min｛j｝ Where ｛a1=bj｝=Min｛j｝ Where ｛a1=bj And j>0 }
=Min｛Min｛j｝ Where ｛a1=bj And j>0 ｝，MaxValue｝
=Min｛Min｛j｝ Where ｛a1=bj And j>L(0,0) ｝，L(1,0)｝
在②中的公式可以寫成
L(1,i)=Min｛Min｛j｝ Where ｛ai=bj｝，L(1,i-1)｝
=Min｛Min｛j｝ Where ｛ai=bj And j>0｝，L(1,i-1)｝
=Min｛Min｛j｝ Where ｛ai=bj And j>L(0,i)｝，L(1,i-1)｝ 此時，1<i≤M
於是，三個公式統一了
④L(k,i)=Min｛Min｛j｝ Where ｛ai=bj And j＞L(k-1,i-1)｝，L(k,i-1)｝ 此時，1≤i≤M，1≤k≤M
且當i＜k時，則L(k,i)=MaxValue
仔細觀察④，公式還可以寫成如下
⑤ L(k,i)=Min｛j｝ Where ｛ai=bj And L(k-1,i-1)<j<L(k,i-1)｝ 1≤i≤M，1≤k≤M，且j存在
或 L(k,i)=L(k,i-1) 1≤i≤M，1≤k≤M，當j不存在時
寫成⑤的目的有兩個：一個是簡化計算，不計算不必要的值；一個是為了標記，為後面計算最長公共子序列做准備。
接下來，將會用例子來說明：
A：481234781；B：4411327431
第一步：初始化L矩陣
第二步：如表格所示，計算第一條對角線
運氣很差，只有第一個單元格有值，其余的都是V（MaxValue），很顯然這不是問題的解。這條對角線滿足L(k-1,i-1)<j<L(k,i-1)的只有一個單元格。先把它標記出來。
第三步：如表格所示，計算相鄰的第二條對角線
運氣比較好，有四個值。說明LCS(A,B)至少是4。但由於對角線上有V（MaxValue），所以本條對角線還不是解。同時，滿足L(k-1,i-1)<j<L(k,i-1)的條件的單元格有3個。把它們標記出來。
第四步：如表格所示，計算相鄰的第三條對角線
同理，這條對角線也不是解。把滿足L(k-1,i-1)<j<L(k,i-1)的單元格標記出來。一共是兩個。
第五步：如表格所示，計算相鄰的第四條對角線
很遺憾，這個還不是解。滿足L(k-1,i-1)<j<L(k,i-1)的解就只有1個。標記出來。
第六步：如表格所示，計算相鄰的第五條對角線
