我正在寻找一种在C++程序中使用的LCS算法实现,需要具有高效的空间利用率。输入是两个整数随机访问序列。
我目前正在使用维基百科关于LCS的动态规划算法实现。然而,这种方法的时间和内存都是O(mn),对于较大的输入数据容易出现内存错误。
我了解到Hirschberg算法、Hunt-Szymanski算法和Masek与Paterson算法可以显著地提高内存利用率。但由于它们不是很容易实现,我更愿意在现有实现中尝试这些算法。请问是否有这样的库?我想既然文本差异工具非常普遍,应该会有一些开源库吧?
char
的临时实现,但没有任何基于Hirschberg线性空间加速或基于元素类型模板化的C++实现)。如果你找到了(或者自己创造了:D)任何东西,请更新! - j_random_hacker