最长公共子序列算法最近想做文件比较（比较两个二进制文件之间的差异,如0 1 2 4 3 5 6和0 1 2 3 4 5比

来源：学生作业帮编辑：拍题作业网作业帮分类：综合作业时间：2024/04/29 02:25:27

最长公共子序列算法
最近想做文件比较（比较两个二进制文件之间的差异,如0 1 2 4 3 5 6和0 1 2 3 4 5比较,结果是0 1 2 +3 4 -3 5 -6）,就要取最长公共子序列（没有+也没有-的部分0 1 2 4 5）.
动态规划O(n²)的方法我会,但是我要处理的是上几MB的文件,用O(n²)的算法显然不行.我需要一个O(nlgn)的算法.

可以用后缀数组搞.
可以看下这个
http://www.cnblogs.com/looker_acm/archive/2010/07/18/1780176.html
再问：你好象搞错了一点，这个算法1234567和1234576算出最长公共子序列是12345，但是我要求的最长公共子序列不一定连续，123456更长
再答：哦，抱歉，我弄错了。公共子序列的话，我不知道有nlgn的算法。我只直到 http://hi.baidu.com/fandywang_jlu/item/b9a9580bbadbbc1aebfe38fd 这个，在一些条件限制下可以达到nlgn的算法，但是最坏情况会更糟。如果你能找到最坏情况还能nlgn的算法，希望可以告诉我。

求两个时间相差的算法如：起始时间 2011-1-1 截止日期 2011-2-1 两个时间比较相差 0年1个月怎么比较两个无穷小量的阶?如A=tanx-x;B=[(2-x^3)/2]-1之间怎么比较? 手头现有1个DNA文件（fasta格式）,序列比较长,可能有100kb,现想从中提取特定位置的序列. 两道指数函数比大小.3/4的负5/6和1比较大小.派的立方和5的负的1.2次方比较大小. 在spss中,对1、2、3、4年级的统一测试结果差异比较要用哪个差异检验?独立样本还是配对样本t检验? 比较-5有6分之5和-4有4分之3的大小（1）利用绝对值来比较大小（2）利用数轴比较（3）中间数比较假设关键字序列为｛9,3,5,1,2,6,4,7,8｝,用直接选择排序算法对关键字进行排序为了比较食用油和水的吸热能力的差异,小明和同学们做了如图所示的实验.（1）在两个相同的容器中... 两个负有理数比大小,(1)求其 (2)比较绝对值的 (3)绝对值大的反而填写成语1、最长的腿----- 2、最遥远的地方----- 3、最荒凉的地方----- 4、最大的差异----- 5、最问两个问题哈,1、简要比较日本与俄罗斯在自然资源和海上航运条件的不同：2、以上差异对日本和俄罗斯... 数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的哪个2趟排序后的结果