在“
文本比较算法Ⅰ——LD算法
”、“
文本比较算法Ⅱ——Needleman/Wunsch算法
”中介绍的LD算法和LCS算法都是基于动态规划的。它们的时间复杂度O(MN)、空间复杂度O(MN)（在基于计算匹配字符串情况下，是不可优化的。如果只是计算LD和LCS，空间占用可以优化到O(M)）。
Nakatsu算法在计算匹配字符串的情况下，有着良好的时间复杂度O(N(M-P))和空间复杂度O(N
2
)，而且在采取适当的优化手段时，可以将空间复杂度优化到O(N)，这是一个很诱人的结果。下面将全面介绍Nakatsu算法。
字符串A和字符串B，计算LCS(A,B)
定义一：设M=Len(A)，N=Len(B)，不失一般性，假设M≤N。（为后面的计算提供方便。若不满足，交换A、B即可）
定义二：A=a
1
a
2
……a
M
，表示A是由a
1
a
2
……a
M
这M个字符组成
B=b
1
b
2
……b
N
，表示B是由b
1
b
2
……b
N
这N个字符组成
LCS(i,j)=LCS(a
1
a
2
……a
i
,b
1
b
2
……b
j
)，其中1≤i≤M，1≤j≤N
定义三：L(k,i)表示，所有与字符串a
1
a
2
……a
i
有长度为k的LCS的字符串b
1
b
2
……b
j
中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 ｛a
i+1
=b
j
And j>L(k-1,i)｝
上面四个定理证明从略。可以从上面四个定理推导出L的计算。
故，L的计算公式为
L(1,1)=Min｛j｝ Where ｛a
1
=b
j
｝
L(1,i)=Min｛Min｛j｝ Where ｛a
i
=b
j
｝，L(1,i-1)｝ 此时，i＞1
L(k,i)=Min｛Min｛j｝ Where ｛a
i
=b
j
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。
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |
|---|---|---|---|---|---|---|---|
| k=1 | |||||||
| k=2 | V | ||||||
| k=3 | V | V | |||||
| k=4 | V | V | V | ||||
| k=5 | V | V | V | V | |||
| k=6 | V | V | V | V | V | ||
| k=7 | V | V | V | V | V | V |
第二步：依据上面的计算公式，计算表格的其余单元格
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |
|---|---|---|---|---|---|---|---|
| k=1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| k=2 | V | 8 | 2 | 2 | 2 | 2 | 2 |
| k=3 | V | V | 11 | 4 | 4 | 4 | 3 |
| k=4 | V | V | V | V | 6 | 6 | 6 |
| k=5 | V | V | V | V | V | 8 | 7 |
| k=6 | V | V | V | V | V | V | 11 |
| k=7 | V | V | V | V | V | V | V |
第三步：在矩阵中找寻对角线
1、先找如下的对角线，对角线中有四个单元格的值是V(MaxValue)。不是本算法的合适答案
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |
|---|---|---|---|---|---|---|---|
| k=1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| k=2 | V | 8 | 2 | 2 | 2 | 2 | 2 |
| k=3 | V | V | 11 | 4 | 4 | 4 | 3 |
| k=4 | V | V | V | V | 6 | 6 | 6 |
| k=5 | V | V | V | V | V | 8 | 7 |
| k=6 | V | V | V | V | V | V | 11 |
| k=7 | V | V | V | V | V | V | V |
2、再找右边的一条对角线。
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |
|---|---|---|---|---|---|---|---|
| k=1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| k=2 | V | 8 | 2 | 2 | 2 | 2 | 2 |
| k=3 | V | V | 11 | 4 | 4 | 4 | 3 |
| k=4 | V | V | V | V | 6 | 6 | 6 |
| k=5 | V | V | V | V | V | 8 | 7 |
| k=6 | V | V | V | V | V | V | 11 |
| k=7 | V | V | V | V | V | V | V |
对角线上的所有单元格的值都不是V(MaxValue)。故本对角线就是算法的求解。
LCS(A,B)就是对角线的长度。故LCS(A,B)=6。
本算法的精妙之处就在于这六个单元格的值所对应的字符串B的字符就是最长公共子串。
最长公共子串：b
1
b
2
b
4
b
6
b
8
b
11
=GATCGA
再将最长公共子串在两个字符串中搜索一遍，能得出字符串的匹配字串。
A：
G
G
A
_
T
C
_
G
__
A
B：
G
A
A
T
T
C
A
G
TT
A
注：原本以为能很容易得出匹配字符串。不过现在看来还需费一番周折，也是考虑不周。不过已经有大概的解决方案，留待后文介绍。
Nakatsu算法关键就是找寻满足条件对角线（对角线的值没有MaxValue）,故计算的过程可以沿着对角线进行，先计算第一条对角线，看是否满足对角线条件，满足则退出，不满足则继续计算下一条对角线，直到计算出满足条件的对角线。
假设LCS(A,B)=P，则一共需要计算M-P+1条对角线，每条对角线的比较次数为N，则Nakatsu算法的时间复杂度为O((M-P+1)N)，空间复杂度为O(M
2
)，但由于计算顺序的优化，可以将空间复杂度降为O(M)，这应该是令人满意的了。有关的Nakatsu算法的优化，留待后文介绍。
本文参考《最长公共子序列的问题的改进快速算法》作者：李欣、舒风笛。在此，向他们表示敬意。
若各位网友谁有更好的文本比较算法，也欢迎写博交流。