matlab 最长公共子序LCS问题编程问题

function [D, dist, aLongestString] = LCS(X,Y)

%%%Calculates the longest common substring between to strings.

%%%Code written by David Cumin

%%%INPUT

%%%X, Y - both are strings e.g. 'test' or 'stingtocompare'

%%%OUTPUT

%%%D is the substring over the length of the shortest string

%%%dist is the length of the substring

%%%aLongestString is a sting of length dist (only one of potentially many)

%%%Make matrix

n =length(X)

m =length(Y)

L=zeros(n+1,m+1)

L(1,:)=0

L(:,1)=0

b = zeros(n+1,m+1)

b(:,1)=1%%%Up

b(1,:)=2%%%Left

for i = 2:n+1

    for j = 2:m+1

        if (X(i-1) == Y(j-1))

            L(i,j) = L(i-1,j-1) + 1

            b(i,j) = 3%%%Up and left

        else

            L(i,j) = L(i-1,j-1)

        end

        if(L(i-1,j) >= L(i,j))

            L(i,j) = L(i-1,j)

            b(i,j) = 1%Up

        end

        if(L(i,j-1) >= L(i,j))

            L(i,j) = L(i,j-1)

            b(i,j) = 2%Left

        end

    end

end

L(:,1) = []

L(1,:) = []

b(:,1) = []

b(1,:) = []

dist = L(n,m)

D = (dist / min(m,n))

if(dist == 0)

    aLongestString = ''

else

    %%%now backtrack to find the longest subsequence

    i = n

    j = m

    p = dist

    aLongestString = {}

    while(i>0 && j>0)

        if(b(i,j) == 3)

            aLongestString{p} = X(i)

            p = p-1

            i = i-1

            j = j-1

        elseif(b(i,j) == 1)

            i = i-1

        elseif(b(i,j) == 2)

            j = j-1

        end

    end

    if ischar(aLongestString{1})

        aLongestString = char(aLongestString)'

    else

        aLongestString = cell2mat(aLongestString)

    end

end

end 示例

>> [D dist str] = LCS('ACGTAACCT', 'GGACTAGG')

>> dist

dist =

     4

>> str

str =

GACT

求解LCS的动态规划算法请自行参阅算法设计书。

SPC即英文

“Statistical

Process

Control”之缩写，意为

“统计制程控制”

SPC或称统计过程控制。SPC主要是指应用统计分析技术对生产过程进行实时监控，科学的区分出生产过程中产品质量的随机波动与异常波动，从而对生产过程的异常趋势提出预警，以便生产管理人员及时采取措施，消除异常，恢复过程的稳定，从而达到提高和控制质量的目的。

LCS是计算机程序中的一种运算方法

LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置。

Ics:额定运行短路分断能力，指按试验程序O-t-CO-t-CO所规定的条件，断路器能继续承载其额定电流能力的分断能力。即断路器仍能够可靠分断的最大短路电流。在切断该短路电流后，断路器仍可以使用。

---