lcs.m

用LCS方法解决字符匹配问题

function [c,b]=LCS(v,w)
v=input('请输入第一个字符串v：');
w=input('请输入第二个字符串w：');
n=length(v);
m=length(w);
s=zeros(n+1,m+1);
for i=1:n
    for j=1:m
        if v(i)==w(j)
            a=s(i,j)+1;
        else a=-Inf;
        end
        [c,d]=max([a,s(i,j+1),s(i+1,j)]);
        s(i+1,j+1)=c;
        if d==1
            b(i,j)='↖';
        else if d==2
                b(i,j)='↑';
            else b(i,j)='←';
            end
        end
    end
end
   PrintLCS(b,v,n,m);
    function PrintLCS(b,v,i,j)
     if i==0|j==0
    return;
end
if b(i,j)=='↖'
    PrintLCS(b,v,i-1,j-1);similarchar(i)=v(i)
    else if b(i,j)=='↑'
         PrintLCS(b,v,i-1,j);
    else
         PrintLCS(b,v,i,j-1);
    end
end