Bus*_*icK 12 c++ algorithm performance dynamic-programming lcs
我正在寻找一种(空间)高效的LCS算法实现,用于C++程序.输入是两个整数的随机访问序列.
我目前正在使用维基百科页面中关于LCS的动态编程方法.但是,它在内存和时间中具有O(mn)行为,并且对于较大的输入而言存在内存错误.
我读过Hirschberg的算法,它大大提高了内存使用率,Hunt-Szymanski和Masek以及Paterson.由于实现这些并非易事,我更愿意在现有实现的数据上尝试它们.有谁知道这样的图书馆？我想,因为文本差异工具很常见,所以应该有一些开源库吗？
搜索此类内容时，请尝试scholar.google.com。对于寻找学术著作要好得多。它出现了 http://www.biotec.icb.ufmg.br/cabi/artigos/seminarios2/subsequence_algorithm.pdf 这个文档，“最长公共子序列算法的调查”。