贡普
gonp是Go中的diff算法实现。
算法
gonp使用的算法基于Sun Wu,Udi Manber和Gene Myers描述的“ O(NP)序列比较算法”。 O(NP)序列比较算法(以下是Wu的O(NP)算法)是比较两个序列的有效算法。
计算复杂度
Wu的O(NP)算法的计算复杂度平均为O(N + PD),最坏的情况是O(NP)。
入门
diff := gonp . New ( "abc" , "abd" )
diff . Compose ()
ed := diff . Editdistance () // ed is 2
lcs := diff . Lcs () // lcs is "ab"
ses := diff . Ses ()
// ses is []SesElem{
// {c: 'a', t: Common},
// {c: 'b', t: Common},
// {c: 'c', t: Delete},
// {c: 'd', t: Add},
// }
例
$ make strdiff
go