在“文本比較算法Ⅰ——LD算法”、“文本比較算法Ⅱ——Needleman/Wunsch算法”中介紹的LD算法和LCS算法都是基於動態規劃的。它們的時間復雜度O(MN)、空間復雜度O(MN)（在基於計算匹配字符串情況下，是不可優化的。如果只是計算LD和LCS，空間占用可以優化到O(M)）。
Nakatsu算法在計算匹配字符串的情況下，有著良好的時間復雜度O(N(M-P))和空間復雜度O(N2)，而且在采取適當的優化手段時，可以將空間復雜度優化到O(N)，這是一個很誘人的結果。下面將全面介紹Nakatsu算法。
字符串A和字符串B，計算LCS(A,B)
定義一：設M=Len(A)，N=Len(B)，不失一般性，假設M≤N。（為後面的計算提供方便。若不滿足，交換A、B即可）
定義二：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)｝ 此時，i＞1
L(k,i)=Min｛Min｛j｝ Where ｛ai=bj And j＞L(k-1,i-1)｝，L(k,i-1)｝ 此時，i＞1，k＞1
注：以上公式中，若找不到滿足Where後面條件的j，則j=MaxValue
當i＜k時，則L(k,i)=MaxValue
MaxValue是一個常量，表示“不存在”
舉例說明：A=GGATCGA，B=GAATTCAGTTA，計算LCS(A,B)
第一步：初始化L矩陣，表格中V=MaxValue。
第二步：依據上面的計算公式，計算表格的其余單元格
第三步：在矩陣中找尋對角線
1、先找如下的對角線，對角線中有四個單元格的值是V(MaxValue)。不是本算法的合適答案
2、再找右邊的一條對角線。
對角線上的所有單元格的值都不是V(MaxValue)。故本對角線就是算法的求解。
LCS(A,B)就是對角線的長度。故LCS(A,B)=6。
本算法的精妙之處就在於這六個單元格的值所對應的字符串B的字符就是最長公共子串。
最長公共子串：b1b2b4b6b8b11=GATCGA
再將最長公共子串在兩個字符串中搜索一遍，能得出字符串的匹配字串。
A：GGA_TC_G__A
B：GAATTCAGTTA
注：原本以為能很容易得出匹配字符串。不過現在看來還需費一番周折，也是考慮不周。不過已經有大概的解決方案，留待後文介紹。
Nakatsu算法關鍵就是找尋滿足條件對角線（對角線的值沒有MaxValue）,故計算的過程可以沿著對角線進行，先計算第一條對角線，看是否滿足對角線條件，滿足則退出，不滿足則繼續計算下一條對角線，直到計算出滿足條件的對角線。
假設LCS(A,B)=P，則一共需要計算M-P+1條對角線，每條對角線的比較次數為N，則Nakatsu算法的時間復雜度為O((M-P+1)N)，空間復雜度為O(M2)，但由於計算順序的優化，可以將空間復雜度降為O(M)，這應該是令人滿意的了。有關的Nakatsu算法的優化，留待後文介紹。
