最长公共上升子序列的另一个O(mn)的算法

    我在这个帖子里说过nlogn求最长上升子序列的方法:
    http://www.oibh.org/bbs/viewthread.php?tid=10682
    下面引用我自己的发言:

     f表示长度为i的上升子序列最后一个数最小是多少。显然数组f是单增的。
     读到一个新的数x后,找到某个i使得x>f[i]且x<=f[i+1],于是用x去更新f[i+1];特别地,如果所有的f[i]都小于x,则增加f的长度。
     最后看f数组有多长就行了。
     由于f单增,所以查找i时可以用二分查找,因此时间复杂度为O(nlogn)。
     举个例子,假如序列为 3 2 8 6 7 4 5 7 3,则f数组的变化过程如下:
     3
     2
     2 8
     2 6
     2 6 7
     2 4 7
     2 4 5
     2 4 5 7
     2 3 5 7
     最后,f的长度达到4,因此答案为4。
     注意,最后的f数组不一定是最长上升子序列的一个方案。

    这里要说的这个算法利用了nlogn的最长上升子序列(LIS)的技巧:用f[k]表示长度为k的上升子序列最后一个数最小是多少。
    在最长公共上升子序列中,令f[i,j][k]表示A串前i个数字,B串前j个数字,长度为k的公共上升子序列中,最后一个数最小是多少。

    当A[i]=B[j]时,像nlogn的最长上升子序列一样把A[i]插入到f[i-1,j]中,这需要线性的时间扫一遍f[i,j];
    当A[i]<>B[j]时,我们需要合并f[i-1,j]和f[i,j-1],使得对于每个k满足f[i,j][k]:=min{ f[i-1,j][k],f[i,j-1][k] }。这需要线性的时间扫一边f[i-1,j]和f[i,j-1]并取k相同时的较小值。
    最后输出f[n,m]的长度(使f[n,m][k]有意义的最大的k)。
    这样的复杂度是三方的,我们需要优化。

    考虑A[i]=B[j]的情况。当i固定时,随着j的增加,插入的位置一定也在后移,因为同样是插入的A[i],但j的增加(B串长度的增加)使得f [i,j]更优,因此可以更新的值就更靠后。于是,对于每个i,我们可以按照k的顺序扫描f[i-1,j][k] 并在A[i]可以插入f[i-1][j]的k位置时增加j,从而预处理所有A[i]=B[j]时A[i]应该插入的位置。
    再考虑A[i]<>B[j]的情况。从定义看,f[i-1,j-1]和f[i-1,j]只有一个地方不一样,因为多一个数最多只能造成一个k 的值变小;同样地,f[i-1,j-1]和f[i,j-1]也只有一个地方不一样。因此,f[i-1,j]和f[i,j-1]最多只有两个k所对应的值不相同,且当有两个不同的值时,总是f[i-1,j]中的某个值较小,f[i,j-1]中的某个值较小。这给我们优化的余地。在每次处理完f[i,j]时,我们可以记录一个值x[i,j]表示f[i,j][k]与f[i-1,j][k]中值不一样的k是多少,在A[i]=B[j]时直接赋值为插入的位置,在 A[i]<>B[j]时待后文说明。以后合并时,先让f[i,j]:=f[i-1,j](由于此时的f[i-1,j]已经没有别的用处了,因此可以用滚动数组记录,直接令f[i-1,j]是f[i,j],避免实际的赋值操作),然后将新的f[i,j]中的,使f[i,j-1][k]比f[i- 1, j][k]小的k所对应值更新。这个k是多少呢?显然应该是x[i,j-1]。这样的操作同时可以确定x[i,j]=x[i,j-1]。
    这样,复杂度就达到了平方。

    附参考的资料(原来从这篇论文里学到的,不知道有没有此类的中文资料,估计没有才在这里写了一个,感兴趣的话可以下载附件仔细研究)

点击下载此文件

Matrix67原创
转载请注明出处

30 条评论

  • fran

    看不懂O(mn)的解释~~能发标程不??

    回复:看一看我提供的原文pdf吧,里面有代码

  • J

    精妙~很好 很强大

  • 晗熙

    问个有关最长不下降序列的问题???
    词链(chain.???)
    问题描述:
    一个词是由至少1个、至多75个小写英文字母组成的。当在一张1个或多个词组成的表中,每一个词(除第一个)都能由在其前一个词的词尾添加1个或多个字母而得到的话,则称此表为一个词链。
    例如下面的表:
    i
    in
    int
    integer
    为一个含四个词的链,而表:
    input
    integer
    不是链。
    一个链的长度是指该链所含词的个数。含一个词的表也是链,其长度为1。

    输入格式:
    你将从输入文件中读到一张表,文件以“.”结束。每行含一个词,表中至少有1个词,而所有词所含字母个数之总和不超过2 000 000个。文件中各行已按字典顺序由小到大排序,且文件中的词不会有重复。

    输出格式:
    你的程序应从输入文件中找出最长的链,并把该链写入到输出文件中。
    要求一个词占一行。
    若有多个最长链,只须输出其中任何一个。

    输入输出举例:
    下面给出了一个由7个词的输入文件和一个对应的输出文件。输入文件中有一个长度为4的链,这里已没有比它更长的链了。
    输入chain.in    
    i
    if
    in
    input
    int
    integer
    output
    .
    输出chain.out
    i
    in
    int
    integer

  • spidermandf

    关于您在论坛发言的那个方法有没标程的…….

  • tomtao26

    最长不下降子序列=最长下降子序列的个数
    有点贪心的味道

  • Broken

    你的附件下不了,能更新一下么?

    BTW,你这些资料哪来的?我怎么就搜不到呢。

  • Reikon

    最长公共上升子序列….没有“公共”吧..

  • Reikon

    我说错了。。。

  • Reikon

    那个pdf文件不能下载哦

  • dfs35123

    当A[i]=B[j]时,像nlogn的最长上升子序列一样把A[i]插入到f[i-1,j]中,这需要线性的时间扫一遍f[i,j];

    为什么是f[i-1,j],不是f[i-1,j-1]?

  • YuMS

    Not Found

    Sorry, but you are looking for something that isn’t here.
    这个是你提供的那个文件提示。。我想看看代码。

  • Greenmoon55

    MS懂了,证明没看,没时间了。要是早点看到就好了,以前一直用N^2的。明天NOIP…

  • haiwei624

    我也是这个疑问
    当A[i]=B[j]时,像nlogn的最长上升子序列一样把A[i]插入到f[i-1,j]中,这需要线性的时间扫一遍f[i,j];

    为什么是f[i-1,j],不是f[i-1,j-1],或是f[i,j-1]?

    还有,当a[i]b[j]时,f[i-1,j]和f[i,j-1]可以合并,是不是因为我们单调的数组里只是存某一位当前最小的值可以是多少,而且合并时并不会增加这个数列的长度?

  • hjss06

    我不认为这是个好方法,有更易理解且更简便的O(mn)算法。

  • pgdlbt

    我没大看懂,但我知道一种O(n^2)的方法{假设两个数列a,b的长度都为n}
    program LCIS;
    var i,n:integer;
       a,b:array[1..3001] of integer;
       f:array[1..3001] of integer;
    procedure dp;
    var i,j,max:integer;
    begin
    fillchar(f,sizeof(f),0);
    for i:=1 to n do
       begin
       max:=0;
       for j:=1 to n do
         begin
         if (a[i]>b[j])and(f[j]>max) then max:=f[j]
         else if (a[i]=b[j])and(f[j]max then max:=f[i];
    writeln(max);
    end;
    begin
    readln(n);
    for i:=1 to n do read(a[i]); readln;
    for i:=1 to n do read(b[i]);
    dp;
    end.

  • oubeichen

    似乎以具体数值来求的话,楼上的简单的n^2的方法只限于两个全排列。

  • Jackie

    YM神牛,请问,求最长公共子序列时,当两个序列长度不等,而且每个序列里的元素可能不是唯一的时,能不能转化成最长上升子序列来解?怎么转化?thx

  • Teron

    Hello would you mind letting me know which hosting company you’re working with?
    I’ve loaded your blog in 3 completely different
    internet browsers and I must say this blog loads a
    lot quicker then most. Can you suggest a good internet hosting provider at a reasonable price?
    Cheers, I appreciate it!

  • slot deposit shopeepay

    WOW just what I was looking for. Came here by searching
    for slot deposit qris

  • slot deposit seabank terbaik

    My brother recommended I might like this blog. He was totally right.

    This post actually made my day. You can not imagine simply how much time I had spent for this information! Thanks!

  • Youssef

    Have you ever thought about adding a little bit more than just your articles?
    I mean, what you say is valuable and all. But
    imagine if you added some great photos or videos to give your posts more, “pop”!

    Your content is excellent but with pics and videos, this site
    could undeniably be one of the most beneficial in its niche.

    Very good blog!

  • Joleen

    Great beat ! I would like to apprentice while you amend your website, how could i subscribe for a blog web site?
    The account helped me a acceptable deal. I had been tiny bit acquainted of this your broadcast offered
    bright clear concept

  • 밤일알바

    Uncertainty mounted more than the economy amid the greater interest
    rates that raised worries about an economic downturn.

    my webpage – 밤일알바

  • 파워볼분석

    Become an Art Huub member and eliminate YouTube/Google
    ads andd YouTube distractions.

    Also visit my site :: 파워볼분석

  • 여성유흥알바

    In Japan, portion-time and temporary workers account for practicfally
    40% of the workforce but hhave historically bbeen ignored by the country’s trade unions.

    Here is my webpage: 여성유흥알바

  • mtpolice-01

    Hi there superb website! Does running a blog like this require a massive amount work?

    I have absolutely no expertise in coding but I was hoping
    to start my own blog in the near future. Anyhow, should
    you have any recommendations or tips for new blog owners please share.
    I know this is off subject nevertheless I simply needed to ask.
    Appreciate it!

  • Sales Clothing

    Excellent site you have here.. It’s hard to find good quality writing like yours these days.
    I seriously appreciate people like you! Take care!!

发表评论

  +  24  =  29