最长公共子序列问题.docx下载

字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=（x0，x1，…，xm-1），序列Y=（y0，y1，…，yk-1）是X的子序列，存在X的一个严格递增下标序列（i0，i1，…，ik-1），使得对所有的j=0，1，…，k-1，有 =yj。子序列:例如，X=（a，b，c，b，d，a，b），Y=（b，c，d，b）是X的一个子序列。给定两个字符序列A和B，如果字符序列Z既是A的子序列，又是B的子序列，则称序列Z是A和B的公共子序列。该问题是求两序列A和B的最长公共子序列（LCS）。