最长公共子序列论文2

最长公共子序列 13 计科行知班 张宗雷 2013 一 问题描述 一个序列的子序列 该序列删除若干子序列后得到的序列 最长公共子序列 给定两个子序列 X 和 Y 当另一个序列 Z 既是 X 的子序列又是 Y 的子序 列则称 Z 是 X 和 Y 的公共子序列 当 Z 是最长的一个公共子序列时 Z 称为 X 和 Y 的最长 公共子序列 二 问题分析及推导过程 1 申明两个数组 用于保存比较的两个字符串 由于事先不知字符串大小 故动态 的实现 这里用 C 的容器 2 申明全局变量 二维数组 B 和数组 C 数组 C 用于保存计算 Xi 和 Yi 的 LCS 值 数组 B 保存当前的 C 是从哪个子问题得来的 为此 定义一个枚举类型 用于标 识不同的方向 分别为对角线 向上 向左和向左向上四个方向 3 根据动态规划 实现一个函数 LCS LENGTH 完成的功能是计算数组 B 和 C 具体过程是 先是动态申请二维数组 B 和 C 他们的行列长度都增加 1 目的就 是方便计算 将 C 的第 0 行和第 0 列都赋上 0 即初始化 开始计算 C i j 以 行为主 一次计算 C 的每一个元素 即将两个数组逐一比较 比较时就有两种情 况 分别是若相等时 就将 C i j 设置成 C i 1 j 1 同时将 B i j 设置成 DIAGONAL 若不相等时 比较 C i 1 j 和 C i j 1 的值 又有三种情况 一是 C i 1 j 与 C i j 1 相等 就随便把某一个赋给 C i j 比如 C i 1 j B i j 设 置为 UP LEFT 二是若 C i 1 j 大于 C i j 1 则将 C i 1 j 赋给 C i j 并且 将 B i j 设置成 UP 最后是若 C i 1 j 小于 C i j 1 则将 C i j 1 赋给 C i j 并且将 B i j 设置成 LEFT 4 根据第 3 步骤的结果 就可以找出所有 LCS 了 这里会用到回溯方法 具体实 现可以用栈 也可以用递归 本人使用的是递归 代码简单 易懂 具体实现方 法是 申请一个数组用于保存一个 LCS 这个数组会反复使用 因此 一旦找到 一个就会立即将它输出 再设置一个变量 curpos 标识当前的数组下标 一个变量 len 保存当前 LCS 数组的元素个数 扫描二维数组 B 从最后一个开始 判断 B 的值 有四种情况 当 B 的值是 UP 时 就向上递归 当 B 的值是 LEFT 时 就 向左递归 当 B 的值是向上或是向左时 这是存在两个选择 先左后上 或是先 上后左 当 B 的值是对角线的时 此时 LCS 数组才保存当前的字符 len 加 1 继续沿对角线递归 递归完之后 len 减 1 回溯 若 len 为 LCS 的长度时 就输 出 三 计算求解过程及算法实现 include include include include include using namespace std int C B C 保存计算 Xi 和 Yi 的 LCS 值 B 保存当前的 C 是从哪个子问题得来的 char LCS 保存一个最长公共子序列 int len 0 回溯时用到的统计保存 LCS 数组当前长度 enum DIAGONAL UP LEFT UP LEFT 定义方向 分别是 对角线 向上 向左和向左向上 LCS LENGTH 函数 求出数组 C 和 B void LCS LENGTH vector X vector Y int m int n 计算 C C new int m 动态分配二维数组 B new int m for int i 0 i m i C i new int n B i new int n for i 1 i m i 赋初值 第 0 列 C i 0 0 for int j 0 j n j 第 0 行 C 0 j 0 for i 1 i m i 开始计算 for j 1 j C i j 1 up C i j C i 1 j B i j UP else left C i j C i j 1 B i j LEFT Print LCS 函数 打印出所有的 LCS void Print LCS int B vector X int i int j int curpos int maxLCS ostream k 0 k out LCS k out endl else if B i j DIAGONAL 对角线 LCS curpos X at i 1 len Print LCS B X i 1 j 1 curpos 1 maxLCS out len 回溯 else if B i j UP 向上 Print LCS B X i 1 j curpos maxLCS out else if B i j LEFT 向左 Print LCS B X i j 1 curpos maxLCS out else 向上或向左 Print LCS B X i 1 j curpos maxLCS out 向上 Print LCS B X i j 1 curpos maxLCS out 向左 输出字符串 void out vector iterator beg vector iterator end while beg end cout beg cout endl int main char s vector X Y ifstream fin LCS in 输入文件 char X MAXSIZE Y MAXSIZE int count 0 实验的测试组数 cout Reading the file LCS in endl if fin NULL cout Reading failed endl cout There is no input file endl cout Please make a iuput file use name LCS in and input strings endl else cout Reading succeed count fin get s 过滤一个换行符 cout These are count groups to be tested endl for int z 1 z count z while fin get s while fin get s cout The group z endl out X begin X end out Y begin Y end int m X size 1 int n Y size 1 LCS LENGTH X Y m n int max C m 1 n 1 保存 LCS 的长度 if 0 max 没有最长公共子序列 cout There is no Longest Common Subsequence n endl else LCS new char max cout All the Longest Common Subsequence are endl Print LCS B X m 1 n 1 0 max cout cout endl for int i 0 i m i 释放空间 delete B i delete C i delete B delete C delete LCS X clear Y clear for return 0 四 运行结果 五 计算复杂性分析 如果仅要求出一个 LCS 的长度 而不需要构造一个 LCS 的元素 则只需要 c 的两行 正在被计算的一行和前面一行 也就是说完全可以用 2 min m n 项以及 O 1 的额外 空间来计算一个 LCS 的长度 此时首先要比较出 m n 的大小 利用他们而这种较小的作为存储空间的行 在本次程 序中构造了两个数组vector Common1 Common 利用 Common 来存储正要计算 的 i 行和利用 Common1 来存储需要用到的 i 1 行 计算结束后 便将本行计算结果 Common 中的值赋给上一行 Common1 此时 Common1 中存储的便是 i 行中的计算结果 然后 Common 便可以继续利用 Common1 中存储的值