音乐数据分析：最长公共子序列

若给定序列X={x1，x2，……，xm}，和另一序列Z={z1，z2，……，zk}，Z是X的子序列是指存在一个严格递增下标序列{i1，i2，……，ik}使得对于所有j=1，2，……，k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，，B}的子序列，X中相应的递增下标序列为{2，3，5，7}。

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X={x1，x2，……，xm}和Y={y1，y2，……，yn}，找出X和Y的最长公共子序列。就是最长公共子序列问题。

设序列X={x1，x2，……，xm}和Y={y1，y2，……，yn}的最长公共子序列为Z={z1，z2，……，zk}，则

（1）若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。

（2）若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。

（3）若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中，Xi={x1，x2，……，xi}；Yj={y1，y2，……，yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时c[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下：

利用如下公式，可得到求最长公共子序列的长度程度：

最长公共子序列的举例，假设两个序列分别是A={bacdbd}，B={dbcbadbb}，根据以上算法，算法过程如表3-1所示：

表3-1　最长公共子序列的动态规划算法

通过不断填写表格3-1，可以得到如下表3-2，由表可知，其最长公共子序列的长度为4。(www.xing528.com)

表3-2　动态规划算法求解两序列的最长公共子序列的计算过程

利用表3-2，可以求出两个序列的最长公共子序列，通过在表中画出线路的方法求出所有最长公共子序列，步骤见表3-3：

（1）从（m，n）到（0，0）。

（2）若当前格与左边一格相同，则画向左箭头，若当前格与上边一格相同，则画向上箭头，以上两者都不符合，从当前格到左上格画左上箭头。

（3）从当前格向箭头方向前进一格，对此格进行（2）步骤。

（4）从（m，n）到（0，0）的不同路径中，左上箭头相对应的格的元素构成最长公共子序列。

表3-3　求解最长公共子序列的线路图

实现上述过程对应的C语言代码如下：

很显然，此过程的时间复杂度为：O（m+n）=O（n）。