我试图理解Hunt & McIlroy的算法,但我不明白如何找到k-candidates。
我知道k-candidates是成对的索引,例如:
- A_i = B_j
- P_(ij) > max(P_(i-1, j), P_(i, j-1))
第二点暗示了k-candidates的两个属性:
在文件A的前i行和文件B的前j行中有一个长度为k的公共子序列。对于文件A 的i 行或文件B的j行,没有长度为k的公共子序列。
现在我如何得到纸上的图片?k-候选人是什么?一旦他们找到他们,我就将他们联合起来?
我也在维基百科上搜索过,但它更清楚..谢谢