研究文本比較算法已經一段時間了。把思路重新理了理。
在“文本比較算法Ⅳ——Nakatsu算法”中提到“對角線上的數字就是最長公共子序列的下標”。
在“文本比較算法Ⅶ——線性空間求最長公共子序列的Nakatsu算法”中提到“每行最左邊不為V的數字就是最長公共子序列的下標”。
以上兩個結論，網友Sumtec都提出了質疑，並提出了反例。經過本人的驗算，Sumtec是正確的，我的文章有問題。
不過，不能說Nakatsu算法有問題。在“文本比較算法Ⅶ——線性空間求最長公共子序列的Nakatsu算法”中的前半部分詳細闡述了Nakatsu算法的計算過程，這個是沒有問題的。只是本人急於將其優化成線性空間，而忽視了證明，故而得出了錯誤的結論。
為何執著於Nakatsu算法？還是有原因的。
文本比較算法的核心是什麼？是為了求出兩個文本的最佳匹配。
何為兩個文本的最佳匹配？匹配是兩個文本的對應關系，它包含了相同的部分，包含了相異的部分（增加、刪除、修改）。對於兩個文本來說，匹配不是唯一的。那最佳匹配就是包含了最多的相同部分（最長公共子序列），同時長度又是最短的。
例如：
A：GGATCGA
B：GAATTCAGTTA
最佳匹配為
A：GGA_TC_G__A
B：GAATTCAGTTA
（藍色部分表示相同部分，黑色表示相異部分，下同）
又例如：
A：481234781
B：4411327431
最佳匹配為：
A：48123478_1
B：4411327431
在研究一系列的LD算法和LCS算法後發現，LD算法側重於相異部分，LCS算法側重於相同部分
故曾經有個推論“兩文本A、B的最佳匹配長度為LD(A,B)+LCS(A,B)的值”
很不幸，這個結論又是錯的。給個反例
A：11111112
B：23333333
LD(A,B)=8；LCS(A,B)=1
最佳匹配為：
A：11111112_______
B：_______23333333
最佳匹配的長度為15≠8+1
故兩個文本的相似度的計算公式應該為LCS(A,B)/MATCH(A,B)。MATCH(A,B)表示最佳匹配的長度。
如果只是為了計算一個最長公共子序列。那麼在“文本比較算法Ⅵ——用線性空間計算最大公共子序列（翻譯貼）”中的Hirschberg算法就能很好的解決這個問題。但是要注意的是，不是每個最長公共子序列都能求出最佳匹配的。因此，Hirschberg算法對於求最佳匹配無能為力。
我現在對於求最佳匹配的思路就是求出每一個最長公共子序列，依次算出各自的匹配，從中找到最佳匹配。
我想，這個時候，Nakatsu算法派上用處了。可以知道，當最長公共子序列的長度為P時，Nakatsu算法占用的空間為P(m-P)，是個二次空間，且知道當P為m/2時，占用空間最大，為m2/4。但好處是能遍歷到所有的最長公共子序列（沒有證明）。且每組解的值是指向B的下標，每組解的橫坐標指向A的下標，又省去了計算匹配的時間。
有誰能給出計算最佳匹配的建設性意見嗎？
