江苏龙网

  1. 首页 > 生活 > >

determine the length of longest common subsequence is at least in linear time?

题主应该在美中某学校上EECS 336这门课。好像作业马上就due了，这个答案可能对你没用了，不过我还是说一下一种思路。还是按照标准的LCS方法先建立table计算c，如果计算所有的元素需要O(n^2)，所以我们只计算部分。因为在table中，如果 |i-j| \u0026gt; K 证明这两个sequence已经至少有K个元素不match了，所以不必考虑，令这种情况下的c=0， 不会影响最终输出结果。 这个方法其实就是只计算table中间宽度为K的块对角带，所以计算时间复杂度为O(K*n)。


    推荐阅读


    上一篇：Eclipse 中 java项目中的点击lib文件夹右键build path→config build path 这四个栏目具体啥用处

    下一篇：wxid_开头的微信号咋弄的