在C++中實現LCS/SES的建議

Question

我正在使用LCS算法在C++中實現我自己的差異。在查看LCS算法文件並嘗試查找SES（最短編輯腳本）時，有時候會對某一行進行更改。在下面的圖例中，它只顯示插入和刪除。因此，向後遍歷圖表，您有水平線是刪除，垂直線是插入。你有一個'c'變更案件的情況是什麼？我假設它將是一個水平線，然後是垂直即刪除然後插入將被視爲改變。我沒有看到任何直接創建SES的C++代碼。也許有更好的實現可以獲得O（ND）或更好的時間複雜度，但我不確定如何創建SES而不創建和反轉圖形。我可以實現LCS生成圖形並將其回溯我只是想提前知道創建SES的確切規則，因爲在這種情況下，您可能需要維護2個狀態刪除並插入以被視爲行變化）？看到下面的文件，你會得到一個變化3,4c4,6（見下文）。如果任何人有任何示例代碼正在這樣做，以便它在C++中最大化運行時間與空間，這將有助於作爲參考，尤其是在以下所示的當前比較二進制格式中創建diff輸出方面。我使用這個版本是因爲我在運行時最大化並且爲此犧牲了空間。

看到他們爲榜樣的曲線圖，他們顯示圖形的SES反向文件第3頁

http://www.xmailserver.org/diff2.pdf

在Linux上使用常規DIFF我的變化差異例如

fileA.txt 
a 
b 
c 
d 
e 
f 
g 

fileB.txt 
w 
a 
b 
x 
z 
y 
e 

diff fileA.txt fileB.txt 
0a1 
> w 
3,4c4,6 
< c 
< d 
--- 
> x 
> z 
> y 
6,7d7 
< f 
< g 

Answer 1

基本上不需要'c'或更改功能。您可以從提供SES的LCS樹進行遍歷，並且只需插入和刪除就可以重建兩者。