dp之

比较重叠部分,记录最长相同的长度,即可!

eyounx的上一个帖子好像是说他没看懂。

dim dparray(1 to 1) as integer, L1 as integer, L2 as integer

function LCS( stra as string, strb as string) as integer
   dim i as integer
   L1 = len(stra) : L2 = len(strb)
   redim dparray(1 to L1*L2+L2)      '忘记二维数组了，就这样吧
   for i=1 to L1*L2+L2
      dparray(i) = -1
   next
   LCS = LCS_Sub(stra,strb,1,1)
end function

function LCS_Sub( stra as string, strb as string, indexa as integer, indexb as integer) as integer)
    if stra>L1 OR strb>L2 then
        LCS_Sub = 0
    else
        if dparray(indexa*L1+indexb)<0 then
            if mid(stra,indexa,1)=mid(strb,indexb,1) then
                dparray(indexa*L1+indexb) = 1 + LCS_Sub(stra,strb,indexa+1,indexb+1)
            else
                dim leftLen as integer, rightLen as integer
                leftLen = LCS_Sub(stra,strb,indexa+1,indexb)
                rightLen = LCS_Sub(stra,strb,indexa,indexb+1)
                if( leftlen > rightlen ) then
                    dparray(indexa*L1+indexb) = leftlen
                else
                    dparray(indexa*L1+indexb) = rightlen
                endif
            end if
        end if
        LCS_Sub = dparray(indexa*L1+indexb)
    end if
end function

我手上没有basic编译器，可能有语法错误。

PS：所谓的LCS paper就是在灌水……
完全是瞎写的……